We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Broken Calculator

Difficulty: Medium

Problem Description

There is a broken calculator that has the integer startValue on its display initially. In one operation, you can multiply the number on display by 2, or subtract 1 from the number on display. Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator.

Key Insights

  • The operations available are limited to multiplication by 2 and subtraction by 1.
  • If startValue is greater than or equal to target, the only option is to decrement until you reach target.
  • If startValue is less than target, it may be more efficient to think backwards from target to startValue, considering when to divide by 2 (if even) or increment (if odd).

Space and Time Complexity

Time Complexity: O(log(target))
Space Complexity: O(1)

Solution

To solve the problem, we can approach it in reverse starting from the target value. The idea is to reduce the target by either halving it (if the target is even) or adding 1 (if the target is odd) until we reach the start value. Each operation corresponds to a step in our calculations. When the target becomes less than or equal to the start value, we simply need to decrement to reach the start value.

  1. If the target is even, we can halve it (reverse of multiplying by 2).
  2. If the target is odd, we increment it by 1 (reverse of subtracting 1).
  3. Count the number of operations until the target falls below or equals to the start value.
  4. Finally, if we have to decrement to reach startValue, we add that to our operation count.

Code Solutions

def brokenCalc(startValue: int, target: int) -> int:
    operations = 0
    while target > startValue:
        if target % 2 == 0:
            target //= 2  # If target is even, divide it by 2
        else:
            target += 1   # If target is odd, increment it by 1
        operations += 1
    return operations + (startValue - target)  # Add remaining decrements to reach startValue
← Back to All Questions