319.Bulb Switcher

Tags: [math], [regulation], [simulation]

Link: https://leetcode.com/problems/bulb-switcher/#/description

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given 
n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.

Solution: Math

class Solution(object):
    def bulbSwitch(self, n):
        """
        :type n: int
        :rtype: int
        """
        return int(math.sqrt(n))

Revelation:

• All bulbs are off at very beginning.
• Assumed we index the bulbs based on 1. so all bulbs on the positions: 1, 2, 3, 4, 5, ..., n.
• First round, we make the bulbs on all positions be 'on'.
• Second round, we make the bulbs on 'even' positions be 'off'.
• Third round, we make the bulbs on positions which are multiple of 3 be 'on'.
• If we only look at one position, the operations sequence like 'on' -> 'off' -> 'on'...
• So for one position, if the number of operations is odd, the final state should be 'on'.
• For one position, if the number of operations is even, the final state should be 'off'.
• Because we want to count how many positions' final state are 'on', which is means we need to count how many positions which have odd number of operations.
• There are only two kind of number, one is prime, the other is composite number.
• For prime, it only has two factors, one is '1', the other is itself, so the number of operations for this kind position is even, the final state will be 'off'. For example, the position 7, and 7 is a prime, so 7 is only the multiple of 1 and 7. At beginning, before any operation, the state of all positions are 'off'. At first round, because 7 is the multiple of 1, so '7 position' is operated, and the state become to 'on', then because 7 is the multiple of 7, so at 7 round, the '7 position' is operated, the state become to 'off'. So final state of '7 position' is 'off'.
• For composite number, there are two kinds of composite number, one is that the number of factors of composite number is even, such as 12, whose factors are 1, 2, 3, 4, 6, 12. The other one is that the number of factors of composite number is odd, such as 9, the factors are 1, 3, 9, (because 9 is a 'perfect square' like 3 * 3 = 9). The number of factors are even means there are even times operations, the final state for this kind of positions are 'off'. The number of factors are odd means there are odd times operations, the final state for this kind of positions are 'on', and this kind of number is perfect square.
• So this questions has been converted to find how many 'perfect square' numbers in the range of [1, n], here we don't consider 0.
• The number of 'perfect square' numbers in the range[1, n] is Sqrt(n). The reason is that the 'perfect square' numbers in the range[1, n] is like this: 1, 4, 9, ..., n, and their corresponding square root is 1, 2, 3, ..., Sqrt(n). The number of numbers in 1, 2, 3, ..., Sqrt(n) = Sqrt(n) - 1 + 1 = Sqrt(n).

Note:

• Time complexity = O(1).
• Space complexity = O(1).

Solution: Regulation

class Solution(object):
    def bulbSwitch(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 0:
            raise ValueError('the input is invalid')
        if n == 0:
            return 0

        group_code = 1
        num_of_elem_in_group = 3
        total = 3

        while total < n:
            group_code += 1
            num_of_elem_in_group += 2
            total += num_of_elem_in_group

        return group_code

Revelation:

• List some examples to find the regulation.

Note:

• Time complexity = O(lgn), n is the given input.
• Explanation of the time complexity: from the above algorithm we can see that after k iterations the total gets to n. So time complexity depends on how many iterations. The k times iterations like this:
• The formula of sum of equal difference series: http://baike.baidu.com/item/等差数列求和公式

Time Limited Exceeded: Simulation

class Solution(object):
    def bulbSwitch(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 0:
            raise ValueError('the input is invalid')
        if n == 0:
            return 0
        if n == 1:
            return 1

        bulbs = [True for _ in xrange(n)]
        for i in xrange(1, n):
            for j in xrange(i, n, i + 1):
                bulbs[j] = not bulbs[j]

        counter = 0
        for bulb in bulbs:
            if bulb:
                counter += 1

        return counter

Note:

• Time complexity = O(n^2), n is the given input.