My Python solution without calculating sqrt()


  • 0
    A
    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].


  • 0
    K

    A simpler version of this should be:

    class Solution(object):
        def bulbSwitch(self, n):
            """
            :type n: int
            :rtype: int
            """
            i = 1
            while i ** 2 <= n:
                i += 1
            return i - 1
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.