Solution


  • 0
    C

    Solution 1: Store all states O(n^2)

    A simple solution is to build an array a, where each element a[i] represents the state of bulb at index i, where 1 is 'on' and 0 is 'off'.

    For example, let's suppose we have n = 6 bulbs.

    The initial state would be represented as '000000'

    After round 1, we turn on all the lights
    State: 111111

    After round 2, we turn off every second bulb.
    State: 101010

    After round 3, we toggle every third bulb. This means index 2 (1 becomes 0) and 5 (0 becomes 1) would be toggled.
    Before: 101010
    After: 100011

    We do the same for rounds 4, 5, 6.
    Round 4 State: 100111
    Round 5 State: 100101
    Round 6 State: 100100

    The final state is '100100', which means that we return '2' for our answer.

    The runtime is O(n^2) because we have to iterate through n elements in the array and we do this for n times. Storage is O(n) because we need to store a 0 or 1 for each of the n bulbs.

    Solution 2: Math observation O(1)

    The n^2 solution will time out on large numbers. But we can try to find a pattern that will save us time.

    The number 4 is toggled 'on' in round 1, 'off' in round 2, and 'on' in round 4.
    The number 5 is toggled 'on' in round 1, and 'off' in round 5.
    The number 6 is toggled 'on' in round 1, 'off' in round 2, 'on' in round 3, and 'off' in round 6.

    In order to determine whether a light at index i will be on and off, we need to know whether there are an odd or even number of divisors. Most numbers have divisors that come in pairs. The exception are perfect squares, whose square root doesn't come in pairs.

    Example:
    6 has four divisors 1, 2, 3, 6
    5 has two divisors 1,5
    4 however has three divisors 1, 2, 4

    Since we only care about the lights that are on, it follows that we only need to count the number of perfect squares from 1 to n. This is the same as computing the square root of n, except we need to use the floor operation to convert it to an integer.

    In Python:

    def bulbSwitch(self, n):
        return int(math.sqrt(n))
    

Log in to reply
 

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