class Solution(object): def bulbSwitch(self, n): """ :type n: int :rtype: int """ count = 0 i = 1 while i < n + 1: if i ** 2 <= n: count += 1 else: break i += 1 return count
Consider the position number of all bulbs, starting from 1 to n.
It is actually looking for all the divisor pairs of the position number, for example, say n = 20, [1, 20] [2, 10] [4, 5]. Only in 1, 2, 5, 10, 20 th round, the bulb at position 20 will be toggled.But as all the pairs have two different numbers, the bulb will be off at the last. Only when this number is a perfect square, will it be toggled on. For example, 25, will be toggled at 5th round, but will not be toggled off again by the other number in pair [5, 5].
So all we have to do is find how many perfect squares in range [1, n].