Pythonでstart値をend値に変換するための最小操作回数を求めるプログラム

問題概要

2つの整数 start と end が与えられたとき、次の2種類の操作のみを使って start を end に変換するために必要な最小の操作回数を求めます。

• 値から 1 を引く（デクリメント）
• 値に 2 を掛ける（倍にする）

例として、start = 2、end = 7 の場合を考えてみましょう。このとき出力は 3 になります。具体的には、2 に 2 を掛けて 4 にし、さらに 2 を掛けて 8 にし、最後に 1 を引いて 7 にするという流れです。

解き方のアプローチ

この問題は、end 側から逆算していくことで効率的に解けます。start から end へ向かうのではなく、end を start に近づける方向で考えるのがポイントです。

手順は以下の通りです。

• 操作回数をカウントする変数 ans を 0 で初期化します
• 以下を繰り返し実行します
  • end が start 以下になった場合：残りの差分（start − end）だけ「1を引く」操作が必要なので、ans + start − end を返して終了します
  • end が奇数の場合：end に 1 を加えて偶数にし、ans を 1 増やします
  • それ以外の場合：end を 2 で割り（切り捨て除算）、ans を 1 増やします

なぜ逆算が有効かというと、目標値が大きい場合は「2を掛ける」ことで一気に値を伸ばせる一方、正攻法で start から掛け算を繰り返すと、途中で end を超えてしまう可能性があり、無駄な探索が発生するからです。end を半分に割っていく戦略なら、各ステップでの判断が常に明確になります。

Pythonでの実装例

class Solution:
    def solve(self, start, end):
        ans = 0
        while True:
            if end <= start:
                return ans + start - end
            elif end % 2:
                end += 1
                ans += 1
            else:
                end //= 2
                ans += 1

ob1 = Solution()
start = 2
end = 7
print(ob1.solve(start, end))

入力

start = 2, end = 7

出力

3

計算量について

このアルゴリズムの時間計算量は O(log end) です。end が start より大きい間、毎ループで必ず 2 で割るか 1 を足す処理が行われるため、end は対数的な速度で減少していきます。そのため、非常に大きな値でも高速に動作する点がこの手法の大きな利点です。