[LeetCode] 319. Bulb Switcher

Problem : https://leetcode.com/problems/bulb-switcher/

A naive solution ( Time Limit Exceeded ).  Use bits to represent bulbs.

class Solution:
    def bulbSwitch(self, n: int) -> int:
        if n <= 0:
            return 0
        
        # turn on all bulbs
        bits = [0xFFFFFFFF] * (n // 32 + 1)
        
        for i in range(1, n):
            for j in range(i, n, i+1):
                # toggle bulbs
                bits[j//32] ^= 1 << (j%32)
        
        # count "ON" bulbs
        result = 0
        for i in range(n):
            if bits[i//32] & (1 << (i%32)):
                result += 1
        
        return result

Math solution:

Since a bulb is "OFF" initially,  a bulb ends up with "ON" state if it is switched an odd number of times.

Bulb X is switched in round Y if and only if  Y divides X ( X % Y == 0 ). 

So bulb X ends up with "ON" if and only if it has odd number of divisor.

Divisors come in pairs.  When X = 36, its divisors are (1, 36), (2, 18), (3,12), (4,9), (6,6)

So Bulb 36 will be toggled in round 1, 2, 3, 4, 6, 9, 12, 18, 36.  So Bulb 36 will be "ON" in the end.

So only square numbers have odd number of divisors.

The problem equals to count the square number between 1 to n 

class Solution:
    def bulbSwitch(self, n: int) -> int:
        result = 1
        
        while result * result <= n:
            result += 1
        
        return result - 1