[leetcode] 319. Bulb Switcher解題レポート

タイトルリンク:https://leetcode.com/problems/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 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.

考え方:考え方は一つだけで、開方できる数の個数です.
1つの数が奇数回操作されてこそ、最終的に明るくなることがわかり、1つの数nに対して、1−nのようなペアが現れる操作がある.nがa*bに分解可能であれば、第aホイールおよび第bにおいても1回ずつ操作される.
しかし,n=k*kの場合は1回しか操作されないため,nが1つの数の二乗に分解できる場合にのみ奇数回の操作が起こり,最終的には明るいままであることが分かる.
コードは次のとおりです.

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

参照:http://kinderriven.cn/2015/12/22/319.%20Bulb%20Switcher/