JavaScriptで解く電球のオン・オフ切替問題：nラウンド後に点灯している電球の数を求める

問題の概要

次のような状況を考えてみましょう。

初期状態でオフになっている電球が n 個あります。まず最初に、すべての電球をオンにします。続いて2回目のラウンドでは、2個ごとの電球をオフにします。3回目のラウンドでは、3個ごとの電球をトグル（オフならオンに、オンならオフに）します。

一般に、i 回目のラウンドでは「i 個ごと」の電球をトグルし、最後の n 回目のラウンドでは n 番目の電球だけをトグルします。

ここで求めたいのは、n 回のラウンドがすべて終わった時点で点灯している電球の個数です。入力として n のみを受け取り、結果を返すJavaScript関数を作成してください。

たとえば、関数への入力が次の場合 −

const n = 5;

出力は次のようになります −

const output = 2;

出力の解説

状態配列では、0 が「オフ」、1 が「オン」を表します −

したがって、5回目のラウンドが終わった時点で点灯している電球は2個だけです（1番目と4番目）。

なぜ答えは「平方数の個数」になるのか

この問題には美しい数学的な性質があります。電球 i がトグルされる回数は、i の約数の個数と一致します。約数が偶数個なら最後はオフになり、奇数個ならオンのままです。そして、約数の個数が奇数になるのは、i が平方数（1, 4, 9, 16 …）である場合だけです。

つまり、この問題の答えは「n 以下の平方数の個数」、すなわち ⌊√n⌋ に等しくなります。n = 5 の場合、1 と 4 の2個が該当するため、出力は 2 となります。

コード例

コードは以下の通りです −

const n = 5;
const findOn = (n = 1) => {
   let off = 0;
   let on = n;
   while(off <= on){
      let mid = Math.floor((off + on) / 2);
      if(mid * mid > n){
         on = mid - 1;
      }else{
         off = mid + 1;
    };
  }; 
   return Math.floor(on);
};
console.log(findOn(n));

このコードでは二分探索を利用して、「n を超えない最大の整数の平方根（整数平方根）」を効率的に求めています。探索範囲を半分ずつ絞り込んでいくため、非常に大きな n に対しても高速に動作するのが特徴です。

実行結果

コンソールには次のように表示されます −

2