# Broken Calculator
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/broken-calculator)
Canonical: https://scaleengineer.com/dsa/problems/broken-calculator
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix), [Millennium](https://scaleengineer.com/companies/millennium)
---
## Problem
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_.

**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`

# Approaches
## Brute-force Breadth-First Search (BFS)
This approach treats the problem as finding the shortest path on an implicit graph. The numbers reachable from `startValue` are the nodes, and the two allowed operations (multiply by 2, subtract 1) represent the edges. Since each operation has a cost of 1, Breadth-First Search (BFS) is a suitable algorithm to find the minimum number of operations.
**Time:** O(target). The number of states to explore can be proportional to the `target` value. For the given constraints (`target` up to 10^9), this approach is too slow and will result in a Time Limit Exceeded (TLE) error. · **Space:** O(target). The `queue` and `visited` set can store a number of elements proportional to `target`, leading to a Memory Limit Exceeded (MLE) error for large inputs.
**Pros:** It's a standard and intuitive approach for shortest path problems on unweighted graphs.; Guaranteed to find the optimal solution if it can run to completion.
**Cons:** Extremely inefficient for large input values.; Exceeds time and memory limits for the given constraints.
### Explanation
We start a BFS from `startValue`. We use a queue to keep track of the numbers to visit and a `visited` set to avoid processing the same number multiple times, which would lead to cycles and redundant work. The BFS explores the graph level by level, where each level corresponds to one additional operation. When we first encounter the `target` value, we have found the shortest path, and the current level number is the minimum number of operations required. However, the state space can be very large (up to `10^9`), making a naive BFS impractical due to excessive time and memory consumption. For instance, from `startValue`, we can generate `startValue-1`, `startValue-2`, ..., `1`, which are all potential nodes to explore. This leads to a very wide search tree, and the algorithm is likely to exceed time or memory limits for the given constraints.
### Algorithm
- If `startValue >= target`, the only way to reach `target` is by repeated subtractions. Return `startValue - target`.
- Initialize a queue and add the starting number `startValue` along with its operation count (0).
- Initialize a `visited` set to store numbers that have already been added to the queue, to prevent cycles. Add `startValue` to it.
- While the queue is not empty:
  - Dequeue the current number and its associated steps.
  - If the current number is the `target`, return the steps.
  - Consider the two possible next states:
    - **Multiply:** Calculate `next = current * 2`. If `next` has not been visited and is within a reasonable bound (e.g., `2 * target`), add it to the queue and the `visited` set.
    - **Subtract:** Calculate `next = current - 1`. If `next` is positive and has not been visited, add it to the queue and the `visited` set.

```java
import java.util.Queue;
import java.util.LinkedList;
import java.util.Set;
import java.util.HashSet;

class Solution {
    public int brokenCalc(int startValue, int target) {
        if (startValue >= target) {
            return startValue - target;
        }

        Queue<long[]> queue = new LinkedList<>();
        queue.offer(new long[]{startValue, 0}); // {value, steps}
        
        Set<Long> visited = new HashSet<>();
        visited.add((long)startValue);

        while (!queue.isEmpty()) {
            long[] current = queue.poll();
            long currentValue = current[0];
            int steps = (int)current[1];

            if (currentValue == target) {
                return steps;
            }

            // Operation 1: Multiply by 2
            long nextMultiply = currentValue * 2;
            // A simple bound to prune the search space. If we go far beyond target,
            // it's likely better to subtract. 2*target is a loose but helpful bound.
            if (nextMultiply < 2L * target && !visited.contains(nextMultiply)) {
                queue.offer(new long[]{nextMultiply, steps + 1});
                visited.add(nextMultiply);
            }

            // Operation 2: Subtract 1
            long nextSubtract = currentValue - 1;
            if (nextSubtract > 0 && !visited.contains(nextSubtract)) {
                queue.offer(new long[]{nextSubtract, steps + 1});
                visited.add(nextSubtract);
            }
        }
        
        return -1; // Should not be reached
    }
}
```

## Greedy Approach by Working Backwards
A more efficient approach is to think about the problem in reverse. Instead of transforming `startValue` to `target` with `*2` and `-1` operations, we can transform `target` to `startValue` using the inverse operations: `+1` and `/2` (if `target` is even). This backward approach reveals a greedy strategy.
**Time:** O(log(target)). The `while` loop continues as long as `target > startValue`. In each one or two iterations, `target` is effectively halved. Therefore, the number of iterations is logarithmic with respect to `target`. · **Space:** O(1). This approach uses only a few variables to store the state (`target` and `operations`), requiring constant extra space.
**Pros:** Extremely efficient in both time and space, easily handling large inputs.; The implementation is simple and concise.
**Cons:** The greedy logic of working backwards is not immediately obvious and requires some insight to discover and prove its correctness.
### Explanation
When working backwards from `target` to `startValue`, we want to reduce `target` as quickly as possible.
- If `target > startValue`:
  - If `target` is even, we can either add 1 or divide by 2. Dividing by 2 reduces the number much faster. It can be proven that this is always the optimal choice. In the forward direction, to reach an even `target`, we could come from `target/2` (1 multiplication) or `target+1` (1 subtraction). Reaching `target/2` is always better than or equal to reaching `target+1` since `target/2` is smaller. Thus, the inverse operation (dividing `target` by 2) is the greedy choice.
  - If `target` is odd, we cannot divide by 2. Our only option is to add 1, making it even. This corresponds to a subtraction in the forward direction. For example, to reach an odd `target`, the last operation must have been a subtraction from `target+1`. So we must have reached `target+1` first.
- If `target <= startValue`:
  - At this point, we can no longer use the division operation (as it would take us further from `startValue`). The only way to bridge the remaining gap is by adding 1 repeatedly. This corresponds to `startValue - target` subtraction operations in the forward direction.
This greedy strategy guarantees finding the minimum number of operations in a highly efficient manner.
### Algorithm
- Initialize `operations = 0`.
- While `target` is greater than `startValue`:
  - Increment `operations`.
  - If `target` is even, divide it by 2 (`target /= 2`). This is the inverse of the multiplication operation.
  - If `target` is odd, increment it by 1 (`target++`). This is the inverse of the subtraction operation and makes the number even for a potential division in the next step.
- Once the loop terminates, `target` is less than or equal to `startValue`. The only way to reach `startValue` from `target` (in the forward direction) is by `startValue - target` subtractions.
- The total number of operations is the count from the loop plus the final subtractions: `operations + startValue - target`.

```java
class Solution {
    public int brokenCalc(int startValue, int target) {
        int operations = 0;
        while (target > startValue) {
            operations++;
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target++;
            }
        }
        return operations + startValue - target;
    }
}
```

# Solutions
### Java

```java
class Solution { public int brokenCalc ( int startValue , int target ) { int ans = 0 ; while ( startValue < target ) { if (( target & 1 ) == 1 ) { target ++; } else { target >>= 1 ; } ans += 1 ; } ans += startValue - target ; return ans ; } }
```

### CPP

```cpp
class Solution { public: int brokenCalc ( int startValue , int target ) { int ans = 0 ; while ( startValue < target ) { if ( target & 1 ) { target ++ ; } else { target >>= 1 ; } ++ ans ; } ans += startValue - target ; return ans ; } };
```

### Python

```python
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
```