C++でNからMに到達するまでの最小ステップ数を求める方法

2つの整数NとMが与えられたとき、以下の2種類の操作のみを使ってNからMに到達するために必要な最小ステップ数を求める問題について解説します。

• 数xを2倍にする(xは2*xになる)
• 数xから1を引く(xはx−1になる)

例えば、N = 4、M = 6の場合、答えは2になります。まずNに対して「1を引く」操作を行うと3になり、続けて「2倍する」操作を行うと2 * 3 = 6となり、Mに到達できます。したがって、必要な最小ステップ数は2です。

解法のアプローチ:問題を逆転させる

この問題を効率的に解く鍵となるのは、問題を逆向きに考えることです。NからMへ向かう代わりに、MからNへ向かうと考え直すと、操作は次のように置き換えられます。

• 数が偶数の場合、その数を2で割る
• 数に1を加える

この考え方に基づくと、最小の操作回数は以下のルールで求められます。

• N > M の場合:Mに1を加え続けてNと等しくなるしかないため、答えは単純に両者の差(N − M)となります。
• N < M の場合:MがNより小さくなるまで2で割り続けます。Mが奇数の場合は、先に1を加えて偶数にしてから2で割ります。MがN未満になった時点で、それまでの操作回数に残りの差(N − M)を加えたものが答えになります。

この貪欲法(グリーディーな手法)が正しく機能するのは、2で割る操作の方が1を加える操作よりも数値を大幅に減らせるためです。目標値に近づくまでは可能な限り割り算を行い、超過した分だけ1を足して調整すればよいことになります。

サンプルコード

#include<iostream>
using namespace std;
int countMinimumSteps(int n, int m) {
    int count = 0;
    while(m > n) {
        if(m % 2 == 1) {
            m++;
            count++;
        }
        m /= 2;
        count++;
    }
    return count + n - m;
}
int main() {
    int n = 4, m = 6;
    cout << "Minimum number of operations required: " << countMinimumSteps(n, m);
}

実行結果

Minimum number of operations required: 2

このアルゴリズムの計算量はO(log M)程度であり、Mを繰り返し半分にしていくため、大きな数同士のケースでも高速に動作します。