JavaScriptで解く「2キー操作」問題：「A」をN個表示する最小ステップ数の求め方

問題の概要

まず、次のような状況を想定してください。

最初、メモ帳（テキストエディタ）には文字「A」が1つだけ表示されています。この状態から、1ステップごとに次の2種類の操作のいずれかを実行できます。

• すべてコピー（Copy All） ― メモ帳上に存在するすべての文字をコピーします（部分コピーは許可されません）。

• 貼り付け（Paste） ― 最後にコピーした文字列を貼り付けます。

私たちの課題は、数値numを唯一の引数として受け取るJavaScript関数を作成し、文字「A」をちょうどnum個表示するために必要な最小の操作回数（コピーまたは貼り付けのステップ数）を計算して返すことです。

入出力例

たとえば、入力が次の場合：

const num = 3;

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

const output = 3;

なぜなら、操作の手順は以下の通りになるからです。

• すべてコピー（結果：「A」）

• 貼り付け（結果：「AA」）

• 貼り付け（結果：「AAA」）

アルゴリズムの考え方

この問題は貪欲法（グリーディー・アプローチ）によって効率的に解けます。ポイントは、現在の文字数currに対して、残り必要な文字数(num − curr)がcurrで割り切れる場合にのみ「すべてコピー」を実行するという判断です。それ以外の場合は「貼り付け」で文字を増やしていきます。

実は、この問題の最小ステップ数はnumの素因数の総和と一致することが知られています。たとえばnum = 12なら、12 = 2 × 2 × 3 と素因数分解できるため、答えは 2 + 2 + 3 = 7 ステップとなります。この性質を利用することで、全探索を避けたシンプルな実装が可能になります。

コード例

この問題を解くコードは以下の通りです。

const num = 3;
const minimumSteps = (num = 1) => {
    let [curr, copy, steps] = [1, 0, 0];
    while(curr != num){
        if((copy < curr) && ((num - curr) % curr) == 0) {
            copy = curr;
        }else{
            curr += copy;
        };
        steps += 1;
    };
    return steps;
};
console.log(minimumSteps(num));

コードのポイント

• curr：現在メモ帳に表示されている「A」の個数

• copy：クリップボードに保持している文字列の長さ

• steps：これまでに実行した操作の回数

ループ内では、クリップボードが空（copy < curr）かつ残りの文字数が現在の文字数で割り切れるときだけコピーを行い、それ以外では貼り付けを繰り返します。これにより、常に素因数分解に基づいた最短経路で目的の文字数へ到達できます。

実行結果

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

3

この実装の計算量はO(n)程度であり、素朴な再帰や全探索に比べて大幅に効率的です。「コピー」と「貼り付け」という一見単純な操作の中に、素因数分解という数学的な構造が隠れている点が、この問題の面白さといえるでしょう。