#991

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Broken Calculator

Compute the minimum operations to transform startValue into target using doubling and decrementing, leveraging a greedy strategy effectively.

math greedy

Problem Statement

You are given a broken calculator with an initial integer display startValue. You can perform two operations: multiply the current value by 2 or subtract 1. Determine the minimum number of operations required to reach a given integer target.

Implement a function that, given startValue and target, returns the minimal number of operations. For example, transforming startValue = 2 to target = 3 requires 2 steps: double to 4, then decrement to 3. Constraints: 1 <= startValue, target <= 10^9.

Examples

Example 1

Input: startValue = 2, target = 3

Output: 2

Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2

Input: startValue = 5, target = 8

Output: 2

Use decrement and then double {5 -> 4 -> 8}.

Example 3

Input: startValue = 3, target = 10

Output: 3

Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Constraints

1 <= startValue, target <= 109

Solution Approach

Reverse Greedy Traversal

Instead of moving forward from startValue, work backward from target. If target is even, divide by 2. If target is odd, increment by 1. Repeat until reaching startValue. This reverse approach exploits the greedy choice to minimize total operations efficiently.

Invariant Validation

At each backward step, validate that the operation preserves the possibility of reaching startValue. The invariant ensures halving only occurs when target is even and incrementing when odd, preventing overshoot and guaranteeing correctness for all ranges up to 10^9.

Optimized Step Counting

Count each operation in the reverse traversal without storing intermediate states. This reduces space complexity to O(1) while preserving the O(log target) time complexity, making it suitable for large numbers and interview-ready execution.

Complexity Analysis

Metric	Value
Time	O(\log target)
Space	O(1)

The algorithm runs in O(log target) time because each backward operation roughly halves the target, and O(1) space since no additional structures are used.

What Interviewers Usually Probe

Checks if you can apply a greedy strategy in reverse to minimize operations.
Wants validation of invariants at each step to ensure correctness.
Assesses understanding of O(log target) efficiency for large input ranges.

Common Pitfalls or Variants

Common pitfalls

Trying to move forward greedily can overshoot the target and increase operations.
Failing to handle odd targets properly when halving in reverse.
Overcomplicating with unnecessary data structures instead of counting operations directly.

Follow-up variants

Allow an additional multiply by 3 operation and analyze how the greedy pattern changes.
Compute minimal operations for a range of targets from a fixed startValue.
Introduce negative numbers as targets and adjust the greedy invariant for decrementing.

FAQ

What is the fastest approach to solve Broken Calculator on LeetCode?

Use a reverse greedy strategy: halve target if even, increment if odd, counting steps until reaching startValue.

Why is reverse traversal important in this problem?

Forward doubling can overshoot quickly; working backward ensures minimal steps and preserves the greedy invariant.

Does this approach work for very large numbers?

Yes, the method runs in O(log target) time and O(1) space, suitable for startValue and target up to 10^9.

How do I handle odd targets in the reverse strategy?

Increment odd targets by 1 before halving to maintain the invariant and minimize total operations.

Can GhostInterview explain the greedy choice pattern in Broken Calculator?

Yes, it highlights why halving even targets and incrementing odd ones yields the minimum operation sequence efficiently.

terminal

Solution

Solution 1: Reverse Calculation

We can use a reverse calculation method, starting from $\textit{target}$. If $\textit{target}$ is odd, then $\textit{target} = \textit{target} + 1$, otherwise $\textit{target} = \textit{target} / 2$. We accumulate the number of operations until $\textit{target} \leq \textit{startValue}$. The final result is the number of operations plus $\textit{startValue} - \textit{target}$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        ans = 0
        while startValue < target:
            if target & 1:
                target += 1
            else:
                target >>= 1
            ans += 1
        ans += startValue - target
        return ans

Continue Practicing

#976 largest perimeter triangle #910 smallest range ii #781 rabbits in forest