No.319 Bulb Switcher

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.

思路与想法：

When I came to this problem in the first time, my could only come up with the brute force method. I use numbers 1,2,3...n to model n bulbs and we perform the operation above. When I finished the whole process, I tried to find the pattern in it, so if a bulb is toggled even times, it will be off eventually, otherwise if a bulb is toggled odd times, it will be on eventually. If a factor is square root of number i, then it will only contribute 1 toggle, otherwise, it will contribute 2 toggles (one for factor itself and the other for number/factor). As a result, we need to find the number of factors in every number of 1,2,3...n and decide the final state of this bulb.

public class Solution {
    public int bulbSwitch(int n) {
        int sum = 0;
        if (n == 1) {
            return 1;
        }
        int[] nums = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            nums[i] = helper(i);
        }
        for (int i = 1; i < n + 1; i++) {
            if (nums[i] == 1) {
                sum++;
            }
        }
        return sum;
    }

    private int helper(int n) {
        int count = 0;
        for (int i = 1; i * i <= n; i++) {
            if(n % i == 0) {
                if (i * i == n) {
                    count++;
                } else {
                    count+=2;
                }
            }
        }
        if (count % 2 == 0) {
            return 0;
        }
        return 1;
    }
}

Time Complexity:

O(n^1.5), time limit exceeded, we need to come up with better solution

If we have a closer observation, we can find that if a number is not a square, it always has pairs of factors, for example, 12 has 1 and 12, 2 and 6, 3 and 4. However, a square has odd number of factors since one of the factor is its square root, the problem is just to find the number of square in 1,2...n.

public class Solution {
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n);
    }
}

Time Complexity:

O(1)

2017.5.18