C++で解く「電球スイッチ」問題 ― nラウンド後に点灯する電球の数を求める

n個の電球があり、最初はすべて消えている状態だとします。まず、すべての電球を点灯させます。次に、2番目ごとの電球を消灯します。3ラウンド目では、3番目ごとの電球をトグル（消えていれば点灯、点いていれば消灯）します。同様に、iラウンド目ではi番目ごとの電球をトグルしていき、nラウンド目では最後の1個の電球のみをトグルします。このとき、nラウンド終了後に点灯している電球の数を求めるのがこの問題です。

例えば入力が3の場合、答えは1になります。その過程は以下の通りです。

• 最初、3つの電球は［消灯， 消灯， 消灯］の状態です。
• 1ラウンド後、［点灯， 点灯， 点灯］になります。
• 2ラウンド後、［点灯， 消灯， 点灯］になります。
• 3ラウンド後、［点灯， 消灯， 消灯］になり、点灯しているのは1個だけです。

解き方

この問題はシミュレーションで解こうとするとO(n²)の計算量が必要ですが、実はもっとシンプルな方法があります。それは「nの平方根を返す」というものです。

なぜ平方根で求まるのか？

i番目の電球は、iの約数の個数と同じ回数だけトグルされます。約数が奇数個になるのは、その数が完全平方数（1, 4, 9, 16, …）の場合だけです。つまり、最終的に点灯し続けるのは完全平方数番目の電球であり、n以下の完全平方数の個数、すなわち ⌊√n⌋ が答えになります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};
main(){
    Solution ob;
    cout << (ob.bulbSwitch(3));
}

入力

3

出力

1