Pythonで1つの数を別の数に変換するのに必要な最小操作回数を求めるプログラム

問題の概要

2つの整数 start と end(start < end)が与えられます。次の2種類の操作のみを使って start を end に変換するとき、必要な操作の最小回数を求めるプログラムを作成しましょう。

• 数値に 1 を加える(インクリメント)
• 数値に 2 を掛ける

例として、start = 5、end = 11 の場合を考えます。5 に 2 を掛けて 10 とし、そこへ 1 を加えれば 11 になるため、答えは 2 回となります。

解き方のアプローチ

この問題は、start から順に操作を試すよりも、end から逆算していく貪欲法(グリーディ法)が有効です。end が偶数なら 2 で割り、奇数なら 1 を引いてから 2 で割るという処理を、end が start 以下になるまで繰り返します。最後に残った差分は「1 を加える」操作で埋めます。

1. カウンタ ct を 0 で初期化します。
2. end ÷ 2 が start 以上である間、次の処理を繰り返します。
   • end が奇数の場合：end から 1 を引いて 2 で割り、ct に 2 を加算します。
   • end が偶数の場合：end を 2 で割り、ct に 1 を加算します。
3. ループ終了後、ct に (end − start) を加算します。
4. ct を返します。

Pythonでの実装例

class Solution:
    def solve(self, start, end):
        ct = 0
        while end / 2 >= start:
            if end % 2 == 1:
                end -= 1
                end = end / 2
                ct += 2
            else:
                end = end / 2
                ct += 1
        ct += (end - start)
        return ct

ob = Solution()
print(ob.solve(5, 11))

入力

start = 5, end = 11

出力

2

計算量のポイント

このアルゴリズムは各ステップで end を半分に近づけていくため、時間計算量は O(log end)、空間計算量は O(1) と非常に効率的です。一方、start から幅優先探索(BFS)などで順に操作を試す方法では、最悪の場合 O(end) の時間がかかる可能性があります。大きな数値を扱う場合でも高速に動作する点が、この逆算アプローチの大きな利点といえます。