319. Bulb Switcher

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.

On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.

Return the number of bulbs that are on after n rounds.

Example 1:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off].
So you should return 1 because there is only one bulb is on.

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 1

Code

当一个灯泡被执行偶数次 switch 操作时它是关着的，当被执行奇数次 switch 操作时它是开着的，那么这题就是要找出哪些编号的灯泡会被执行奇数次操作

现在假如我们执行第 i 次操作，即从编号 i 开始对编号每次+i 进行 switch 操作，对于这些灯来说， 如果其编号 j（j=1,2,3,⋯,n）能够整除 i，则编号 j 的灯需要执 switch 操作。 具备这样性质的 i 是成对出现的，比如： j=12 时，编号为 12 的灯，在第 1 次，第 12 次；第 2 次，第 6 次；第 3 次，第 4 次一定会被执行 Switch 操作，这样的话，编号为 12 的等肯定为灭。 但是当完全平方数 36 就不一样了，因为他有一个特殊的因数 6，这样当 i=6 时，只能被执行一次 Switch 操作，这样推出，完全平方数一定是亮着的， 所以本题的关键在于找完全平方数的个数

(int)Math.sqrt(n) 这样可以找出有0-n之间有多少个完全平方数 比如n=37有1,2,3,4,5,6这几个完全平方数，所以结果等于6

class Solution {
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }
}

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(math.sqrt(n))