Pythonで解く「壊れた電卓」問題 ― 最小操作回数を求める逆算アルゴリズム

問題の概要

ある「壊れた電卓」があるとします。ディスプレイには何らかの数字が表示されていますが、私たちが実行できる操作は次の2つだけです。

• 2倍（Double） … ディスプレイに表示されている数字を2倍にする
• 1減らす（Decrement） … ディスプレイに表示されている数字から1を引く

初期状態では、電卓には数字 X が表示されています。ここで、数字 Y を表示させるために必要な最小の操作回数を求めてください。

例えば、入力が X = 5、Y = 8 の場合、答えは 2 になります。これは「1減らして4にする」→「2倍して8にする」という2回の操作で目的の値に到達できるためです。

解法のアプローチ：逆算で考える

XからYへ向かって順に操作を試す方法も考えられますが、組み合わせが膨大になり非効率です。そこで有効なのが逆算（バックワード）の発想です。目標値Yから出発し、Xに近づくまで操作を巻き戻していきます。

逆算時のルールは次の通りです。

• Yが偶数の場合：2倍の逆操作である「半分にする」（Y ÷ 2）が最短経路になります。
• Yが奇数の場合：2倍した結果は必ず偶数になるため、奇数Yは「1減らす」操作の結果と考えるしかありません。つまり逆操作は「1足す」（Y + 1）となります。

そして、YがX以下になった段階で、残りは「1減らす」操作を (X − Y) 回繰り返すだけで到達できます。

アルゴリズムの手順

1. 操作回数を記録する変数 res を0で初期化します。
2. Y > X の間、以下を繰り返します。
   • res += Y % 2 + 1 を実行（奇数なら2回分、偶数なら1回分としてカウント）
   • Yが偶数なら Y // 2、奇数なら (Y + 1) // 2 で更新
3. 最後に res + X - Y を返します。

Pythonでの実装例

以下の実装を見ると、理解がより深まるでしょう。

class Solution(object):
    def brokenCalc(self, X, Y):
        res = 0
        while Y > X:
            res += Y % 2 + 1
            Y = Y // 2 if Y % 2 == 0 else (Y + 1) // 2
        return res + X - Y

ob = Solution()
print(ob.brokenCalc(5, 8))

入力例

5
8

出力例

2

計算量について

このアルゴリズムの時間計算量は O(log Y)、空間計算量は O(1) です。Yを繰り返し半分に近づけていくため、必要な操作回数は対数オーダーに収まり、大きな数に対しても非常に効率的に動作します。