JavaScriptで数値を最小回数の操作で1にする方法

問題概要

整数 num を引数として受け取り、以下の2種類の操作だけを使って num を 1 まで減らすとき、必要な最小の操作回数を求めるJavaScript関数を作成します。

• num が偶数の場合： num を num / 2 に置き換えることができます。

• num が奇数の場合： num を num + 1 または num - 1 のどちらかに置き換えることができます。

これらの操作を組み合わせて num を 1 に到達させ、その最小手数を関数の戻り値として返します。

入出力例

例えば、関数への入力が次の値だったとします。

const num = 7;

この場合の出力は以下のようになります。

const output = 4;

出力の解説

7 を 1 にする最短の手順は次の2通りがあります。

7 -> 8 -> 4 -> 2 -> 1
または
7 -> 6 -> 3 -> 2 -> 1

いずれの経路でも操作は 4 回で済むため、答えは 4 となります。

実装コード

この問題は幅優先探索（BFS）を使うことで効率的に解けます。各ステップで到達可能な数値をキューに追加し、すでに訪問した数値を Set で管理することで、同じ状態の再探索を防いでいます。

const num = 7;
const downToOne = (num = 1) => {
   let min = Number.POSITIVE_INFINITY;
   let stack = [{ num: num, step: 0 }];
   let set = new Set();
   let next;
   let item;
   while (stack.length) {
      item = stack.shift();
      if (item.num === 1) {
         if (min > item.step) {
            min = item.step;
         }
         continue;
      }
      if (set.has(item.num) || item.step >= min) {
         continue;
      }
      set.add(item.num);
      next = item.step + 1;
      if (item.num % 2 === 0) {
         item.num /= 2;
         stack.push({ num: item.num, step: next });
      } else {
         stack.push({ num: item.num - 1, step: next });
         stack.push({ num: item.num + 1, step: next });
      }
   }
   return min;
};
console.log(downToOne(num));

コードのポイント

• BFS（幅優先探索）： キューを使って各段階の状態を順番に処理することで、最初に 1 に到達した時点の手数が最短であることが保証されます。

• Set による重複排除： 一度訪れた数値を記録し、同じ状態を何度も探索しないようにして計算量を抑えています。

• 枝刈り： 現時点で判明している最小手数（min）以上のステップは探索せずスキップすることで、さらに処理を高速化しています。

出力結果

コンソールには次のように出力されます。

4