C++で解く整数置換問題：1になるまでの最小操作回数を求めるアルゴリズム

正の整数 n が与えられ、これに対して次の操作を繰り返し適用できるものとします。

• n が偶数の場合：n を n / 2 に置き換える
• n が奇数の場合：n を n + 1 または n - 1 のいずれかに置き換える

このとき、n を 1 にするまでに必要な最小の操作回数を求めるのが本問題です。

問題の例

たとえば n = 7 の場合、答えは 4 になります。次のような操作列が存在するからです。

• 7 → 8 → 4 → 2 → 1
• 7 → 6 → 3 → 2 → 1

解法のアプローチ（貪欲法）

この問題は、以下の手順で貪欲に解くことができます。

1. ret := 0、n := x と初期化する
2. n > 1 の間、次を繰り返す
   • n が偶数なら、n := n / 2 とする
   • n が奇数なら、n == 3 または n / 2 が偶数（つまり n % 4 == 1）の場合は n を 1 減らし、それ以外の場合は 1 増やす
   • ret を 1 増やす
3. 最後に ret を返す

なぜこの戦略が有効か

n が奇数で n % 4 == 3 を満たすとき、n + 1 とすると 4 の倍数になるため、2 回連続で 2 による除算が可能になり、結果として少ない操作で済みます。一方、n == 3 の場合は例外で、3 → 2 → 1（2 回）とする方が 3 → 4 → 2 → 1（3 回）よりも短いため、必ず減算を選びます。また、オーバーフロー防止のため n は long long 型で扱っている点にも注目してください（n = INT_MAX のとき n + 1 が発生する可能性があるためです）。

C++での実装例

以下のコードで、実際の動作を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    int bitCount(int x){
        int ret = 0;
        while(x){
            ret++;
            x >>= 1;
        }
        return ret;
    }
    int integerReplacement(int x) {
        int ret = 0;
        lli n = x;
        while(n > 1){
            if(n % 2 == 0){
                n >>= 1;
            }
            else if(n & 1){
                if(n == 3 || (((n >> 1) & 1 )== 0)){
                    n--;
                } else {
                    n++;
                }
            }
            ret++;
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.integerReplacement(7));
}

入力

7

出力

4

まとめ

本アルゴリズムでは、各ステップで n を半分以下に減らしていくため、計算量は O(log n) となります。ビット演算を活用した判定により、シンプルかつ高速に最小操作回数を求められるのがポイントです。