JavaScriptでmからnに到達するための最小操作回数を求めるアルゴリズム

問題

2つの数値 m と n を引数として受け取るJavaScript関数を作成します。関数は、m の状態から開始して n に到達するまでに必要な最小の操作回数を求めて返します。

使用できる操作は、次の2つだけです。

• 2倍(Double) – 表示中の数値を2倍する
• デクリメント(Decrement) – 表示中の数値から1を引く

たとえば、次のように関数を呼び出した場合を考えてみましょう。

const m = 5;
const n = 8;

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

const output = 2;

出力の解説

m = 5 から n = 8 へは、次の手順で2回の操作で到達できます。

5 → 4 → 8

まず「デクリメント」で5を4にし、続いて「2倍」で4を8にします。これより少ない操作回数で8へ到達する方法は存在しないため、正解は2となります。

考え方:逆算アプローチ

この問題を効率的に解く鍵は、n から m へ向かって逆算することです。前方の操作「2倍」「−1」に対して、逆方向では次のように対応させられます。

• n が偶数の場合 → 2で割る(直前のステップで2倍されたと考えられるため)
• n が奇数の場合 → 1を足す(偶数にしてから2で割れるようにする)
• n が m 以下になったら → 残りの差(m − n)のぶんだけデクリメントを行う

この手法により、全パターンを探索する必要がなくなり、非常に高速に答えを導き出せます。while ループの各ステップで n はおおむね半分以下に減っていくため、計算量は O(log n) 程度に収まります。

コード例

上記のロジックを実装したコードがこちらです。

const m = 5;
const n = 8;
const findOperations = (m, n) => {
   let res = 0;
   while(n > m){
      if(n % 2 === 0){
         n /= 2;
      }else{
         n += 1;
      };
      res += 1;
   };
   return res + m - n;
};
console.log(findOperations(m, n));

コードのポイントは次のとおりです。

• n が m より大きい間、偶数なら2で割り、奇数なら1を足して操作回数をカウントします。
• ループを抜けた時点で n ≤ m になっているため、「res + m - n」で残りに必要なデクリメント回数を加算して返します。

出力

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

2

このように、逆算の発想を使えば一見複雑に思える最小操作回数の問題も、シンプルで効率的なコードで解決できます。