319. Bulb Switcher

Question

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.

Return the number of bulbs that are on after n rounds.

Solution

Each position is only switched on its factor rounds, and factors appear in pairs except when squared, where the factor is the same. Therefore, the problem is equivalent to finding the number of times a perfect square appears.

每个位置只在其因子回合会被切换，除了平方时因子相同，其他时候因子都是成对出现的。因此改题目等价于求平方数出现次数。

Code

class Solution {
public:
    int bulbSwitch(int n) {
        // bulbs will switch in factor round
        // since factor round will appear with pair
        // we just need to count square round

        return (int) sqrt(n);
    }
};