Vultr DocsLatest Content

Broken Calculator

Updated on 15 May, 2025
Broken Calculator header image

Problem Statement

The Broken Calculator problem presents a scenario where you initially have an integer startValue shown on a defective calculator screen. This calculator has only two functional operations: doubling the present value or subtracting one from it. The challenge is to compute the minimum number of operations required to manipulate the startValue to make it equal to another given integer target. This problem requires us not only to transform the number but to do it using the fewest steps possible.

Examples

Example 1

Input:

startValue = 2, target = 3

Output:

2

Explanation:

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

Example 2

Input:

startValue = 5, target = 8

Output:

2

Explanation:

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

Example 3

Input:

startValue = 3, target = 10

Output:

3

Explanation:

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

Constraints

  • 1 <= startValue, target <= 109

Approach and Intuition

Here's a breakdown based on the examples provided:

Example Analysis

  1. Example 1:

    • Start Value: 2
    • Target: 3
    • Doubling 2 gives us 4, and then subtracting 1 brings us down to 3, resulting in two operations: Double, then subtract.

  2. Example 2:

    • Start Value: 5
    • Target: 8
    • Reducing 5 to 4 and then doubling the result gets us exactly to 8, taking two steps: Subtract, then double.

  3. Example 3:

    • Start Value: 3
    • Target: 10
    • In this scenario, doubling 3 first gets us to 6. Reducing 6 to 5 and doubling again reaches 10. This took three operations: Double, subtract, and double.

Intuitive Strategy

  • Reverse Thinking: Although one might consider starting from startValue and reaching target while keeping the operations to a minimum, it can be computationally effective to think reversely. Starting from target and trying to reach startValue using reverse operations (considering addition for subtraction and halving for doubling when possible) might simplify and reveal quicker paths in specific scenarios.

  • Edge Conditions: When target is greater than startValue, the choice isn't always straightforward; as seen, sometimes subtracting first (even though it gets you further from the target) can provide a shorter path after a subsequent double operation.

This reverse strategy and consideration of non-intuitive operations can help in designing an effective algorithm to solve this problem considering the constraints provided (1 <= startValue, target <= 109). The constraint bounds suggest that the solution should efficiently handle large numbers, and avoid solutions growing exponentially with the inputs.

Solutions

  • Java
  • Python
java 
class Solution {
    public int minimalSteps(int initialValue, int goal) {
        int stepCount = 0;
        while (goal > initialValue) {
            stepCount++;
            if (goal % 2 == 1)
                goal++;
            else
                goal /= 2;
        }

        return stepCount + initialValue - goal;
    }
}

The provided Java solution addresses the problem of calculating the minimum number of operations required to transform an initial value to a specified goal using a broken calculator. The calculator can either decrement the value by one or divide the value by two if it is even. The method minimalSteps takes two integers, initialValue and goal, as parameters and uses a while loop to process the goal until it becomes less than or equal to the initialValue.

Here's a brief overview of the core logic behind the solution:

  • Initialize stepCount to 0 which keeps track of the number of operations performed.
  • Use a while loop to iterate as long as goal is greater than initialValue.
    • Increment stepCount by one every iteration to count the operation.
    • If goal is odd, increment goal by one to make it even (this simulates the button press that changes the goal).
    • If goal is even, halve the goal.
  • After exiting the loop, add the difference between initialValue and the modified goal to the stepCount, accounting for any direct decrements needed to match the initialValue.

This solution gracefully handles the operation counting and efficiently reaches the target using the minimal steps by leveraging the faster reduction capability of division over subtraction.

python 
class Solution:
    def calculateSteps(self, initialValue: int, goal: int) -> int:
        steps = 0
        while goal > initialValue:
            steps += 1
            if goal % 2 == 1:
                goal += 1
            else:
                goal //= 2

        return steps + initialValue - goal

In the "Broken Calculator" problem, the task is to determine the number of steps needed to transform a given initial value into a goal value using a specific set of operations. For each operation, you can either decrement the calculator's display by 1 or, if the number is even, you can divide the display number by 2.

Here is a comprehensive summary of how the provided Python code solves the problem:

  • Start by setting up a variable steps to count the operations performed.
  • Use a while loop to repeatedly process the goal value until it goes no higher than the initial value.
  • Inside the loop, if the goal value is odd, increase it by 1 (to make it even making halving possible in subsequent steps). Each adjustment or halving action increments the step count.
  • If the goal value is even, divide it by 2.
  • After the loop, account for any remaining difference between the initial value and the current goal by adding the difference to the step count. This accounts for cases where direct decrementation from the initial value to the goal is more efficient than division sequences.

This approach efficiently handles both incrementing towards even numbers suitable for division and minimizing steps through direct subtraction, presenting a blend of strategic decrements and divisions to reach the target efficiently.

Comments

No comments yet.