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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Broken Calculator

Number: 1033

Difficulty: Medium

Paid? No

Companies: Nutanix

Problem Description

Given two integers startValue and target, the goal is to transform startValue into target using a broken calculator that supports only two operations: multiplying the current number by 2 and subtracting 1. Determine the minimum number of operations required to achieve exactly target from startValue.

Key Insights

  • Reverse the process from target to startValue instead of simulating the forward operations.
  • If target is even, divide it by 2 (which is the reverse of multiplying by 2).
  • If target is odd, increment it by 1 (which is the reverse of subtracting 1).
  • Once target is less than or equal to startValue, the remaining difference can be added directly as only subtraction operations are required.

Space and Time Complexity

Time Complexity: O(log(target) + (startValue - target)) in the worst case. Space Complexity: O(1)

Solution

The approach is to work backwards from target to startValue:

  1. If target is greater than startValue, check if it is even. If yes, divide by 2 (reversing the multiplication operation).
  2. If target is odd, increment it by 1 (reversing the subtraction operation).
  3. Count every operation until target is less than or equal to startValue.
  4. Once the loop ends, add the difference (startValue - target) to the total operations as only decrements are needed. This method minimizes operations and avoids inefficient forward traversal.

Code Solutions

# Function to calculate the minimum operations for the broken calculator
def brokenCalc(startValue, target):
    operations = 0
    # While target is greater than startValue, apply reverse operations
    while target > startValue:
        # If target is even, it is optimal to divide by 2
        if target % 2 == 0:
            target //= 2
        else:
            # If target is odd, add 1 to make it even (reverse of subtracting 1)
            target += 1
        operations += 1
    # Once target is less or equal to startValue, the rest are decrement operations
    return operations + (startValue - target)

# Example usage
print(brokenCalc(2, 3))  # Output: 2
print(brokenCalc(5, 8))  # Output: 2
print(brokenCalc(3, 10)) # Output: 3
← Back to All Questions