Domain 2MediumMEDIUM

Broken Calculator

LeetCode problem 991: Broken Calculator (medium).

Domain: medium•Updated: 2026-09-06
#Math#Greedy

Problem Breakdown

Restatement: We start with a number X on a broken calculator display. The only allowed operations are doubling the current value (* 2) or decrementing it by one (- 1). Our goal is to reach exactly Y. We need to find the minimum sequence of these two operations required to transform X into Y.

Inputs & Outputs:

  • Input: Two integers, start (X) and target (Y), where 1≤X,Y≤1091 \le X, Y \le 10^9.
  • Output: An integer representing the minimum number of operations.

Constraints & Edge Cases:

  • Large Numbers: Since values can reach 10910^9, an approach that iterates linearly (e.g., decrementing one by one from X to Y) will result in Time Limit Exceeded (O(N)O(N)). We need a logarithmic or better solution.
  • X > Y: If the starting number is already larger than the target, we cannot double without overshooting significantly. The only viable operation is decrementing until Y. Cost = ∣X−Y∣|X - Y|.
  • Parity Handling: Doubling always results in an even number. This implies that if our current backward state (working from Y) is odd, it could not have been reached by a doubling operation immediately prior; it must be the result of a decrement followed by other operations or simply being incremented back up to reach X via decrements.

Intuition

Brute Force: A naive Breadth-First Search (BFS) from X exploring both double and decrement branches would explore an exponential state space relative to the value magnitude, leading to O(2N)O(2^N) or at least very high constant factors due to redundant paths. Given constraints up to 10910^9, this is infeasible.

Key Insight (Reverse Greedy): Instead of trying to build Y from X, consider working backwards from target Y to start X. The inverse operations are:

  • Inverse of Double (×2\times 2) →\rightarrow Divide by 2 (/2/ 2).
  • Inverse of Decrement (−1-1) →\rightarrow Increment (+ 1).

When working backwards from a larger number Y to a smaller target X:

  1. Divide: If the current value is even and greater than X, dividing by 2 reduces the magnitude significantly faster than incrementing or decrementing (in forward terms) would allow us to reach X efficiently. This corresponds to reversing a “Double” operation which was cheap in cost but high impact on value.
  2. Increment: If the current value is odd, we cannot divide it by 2 cleanly without losing information relative to the doubling history. An even number must have come from a double (or an increment if going backward). Since forward operations are *2 and -1, any odd target in our reverse path implies the last step was likely a decrement (B→B−1B \to B-1), so we must “undo” that by Incrementing (+ 1) to make it even, then divide.

Greedy Strategy: While the current value curr > X:

  • If odd: We must increment (+1) (inverse of decrement). This costs 1 op and makes the number even for division next step.
  • If even: Divide by 2 (/2). This reduces distance to X most aggressively.

Once curr <= X, we have overshot or reached a point where only decrements remain in forward logic (increments in backward). The remaining difference is simply added as operations.

Approach

  1. Handle Base Case: If X >= Y, the target is smaller than start. We can’t double without overshooting past X significantly, so we just decrement until match. Return X - Y.
  2. Initialize Variables: Set a counter for operations (ops = 0) and set current working value to Y (or simply manipulate curr). Let’s use curr initialized to target. However, the standard logic is often cleaner if we just track ops while reducing curr. Wait, actually simpler:
    • If X >= Y: return abs(X - Y).
  3. Backward Loop: While Y > X:
    • Check parity of Y (or current working value).
    • If odd (Y % 2 != 0): Increment Y, increment ops count. This simulates undoing a decrement from the forward pass.
    • If even: Divide Y by 2, increment ops count. This undoes a double operation.
  4. Final Adjustment: Once loop terminates (curr <= X), we are at some value smaller than or equal to start. The remaining gap must be filled with decrements (forward) / increments (backward). Add X - curr to total operations and return sum.

Complexity Analysis

  • Time Complexity: O(log⁡Y)O(\log Y). In each step of the loop, we either divide by 2 or increment once then divide in next iteration. The value decreases exponentially towards X due to division steps. Even with increments for parity correction, it doesn’t increase complexity beyond logarithmic relative to Y.
  • Space Complexity: O(1)O(1). We only use a few integer variables regardless of input size.

Solution

def brokenCalc(X: int, Y: int) -> int:
    ops = 0
    
    # If start is already greater than or equal to target, 
    # we can only decrement (inverse increment in backward view).
    if X >= Y:
        return X - Y

    curr = Y
    while curr > X:
        # Working backwards from Y. We want to reduce 'curr' towards X.
        # If odd, it must have come from a Decrement operation (inverse is Increment) 
        # because doubling always results in an even number.
        if curr % 2 == 1:
            ops += 1      # Inverse of decrement (+1)
            curr += 1     # Make it even for division next step
        
        else:
            ops += 1      # Inverse of double (/2)
            curr //= 2
    
    # If we dropped below X via division, the remaining difference 
    # must be covered by decrements (inverse increments).
    return ops + (X - curr)

Edge Cases Handled

  • X >= Y: The code immediately returns abs(X - Y) because doubling is impossible without overshooting. This handles cases like Example 4 (1024 -> 1).
  • Odd Target: If the target (or intermediate backward value) is odd, we increment it to make it even before dividing. This correctly accounts for the necessary decrement operation in the forward pass that created this parity mismatch.
  • Large Inputs (10910^9): The logarithmic reduction ensures execution time remains well within limits despite large integer values. Python handles arbitrary precision integers automatically preventing overflow issues common in fixed-width languages, though logic holds regardless of bit-size here.