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
After round 2, we turn off every second bulb.
After round 3, we toggle every third bulb. This means index 2 (1 becomes 0) and 5 (0 becomes 1) would be toggled.
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.
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.
def bulbSwitch(self, n): return int(math.sqrt(n))