# LeetCode 991: Broken Calculator

## Problem Restatement

We are given two integers:

```python
startValue
target
```

A broken calculator starts by displaying `startValue`.

It supports only two operations:

| Operation | Effect |
|---|---|
| Double | Multiply the current number by `2` |
| Decrement | Subtract `1` from the current number |

We need to return the minimum number of operations needed to display `target`.

The official constraints are:

| Constraint | Value |
|---|---:|
| `startValue` | `1 <= startValue <= 10^9` |
| `target` | `1 <= target <= 10^9` |

Source: LeetCode 991 problem statement.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integers `startValue` and `target` |
| Output | Minimum number of operations |
| Forward operations | `x * 2` or `x - 1` |
| Goal | Transform `startValue` into `target` |

Function shape:

```python
def brokenCalc(startValue: int, target: int) -> int:
    ...
```

## Examples

Example 1:

```python
startValue = 2
target = 3
```

One optimal sequence is:

```python
2 -> 4 -> 3
```

Answer:

```python
2
```

Example 2:

```python
startValue = 5
target = 8
```

One optimal sequence is:

```python
5 -> 4 -> 8
```

Answer:

```python
2
```

Example 3:

```python
startValue = 3
target = 10
```

One optimal sequence is:

```python
3 -> 6 -> 5 -> 10
```

Answer:

```python
3
```

## First Thought: Search Forward

One direct way is to search from `startValue`.

At every number, we can try:

```python
x * 2
x - 1
```

Then we search until we reach `target`.

This resembles BFS, because each operation has cost `1`.

But the values can go up to `10^9`, so searching through possible values is too large and unnecessary.

## Key Insight

Instead of going forward from `startValue` to `target`, work backward from `target` to `startValue`.

The forward operations are:

| Forward | Reverse |
|---|---|
| `x * 2` | `x / 2` |
| `x - 1` | `x + 1` |

Working backward gives a simple greedy rule.

If `target` is even, divide it by `2`.

If `target` is odd, add `1` to make it even.

Why?

When `target` is even, dividing by `2` makes the number much smaller in one operation. This reverses a useful double operation.

When `target` is odd, it cannot be reached by doubling an integer. So the last forward operation must have been decrement. Reversing that means adding `1`.

We repeat until `target <= startValue`.

At that point, going backward further by division is no longer needed. Forward from `startValue` to this smaller `target` only requires decrements:

```python
startValue - target
```

## Algorithm

Initialize:

```python
operations = 0
```

While `target > startValue`:

1. If `target` is even:
   ```python id="w42d7w"
   target //= 2
   ```
2. Otherwise:
   ```python id="pe3t6g"
   target += 1
   ```
3. Increment `operations`.

After the loop, `target <= startValue`.

Add the remaining decrement operations:

```python
operations += startValue - target
```

Return `operations`.

## Correctness

Consider the reverse process from `target` to `startValue`.

If the current `target` is odd and greater than `startValue`, the previous forward operation could not have been doubling, because doubling always produces an even number. Therefore, the previous forward operation must have been decrement. In reverse, we must add `1`.

If the current `target` is even and greater than `startValue`, reversing a double operation by dividing by `2` is always optimal. It reduces the value faster than adding `1`, and it directly undoes a possible forward double operation.

The algorithm applies these forced or greedy reverse choices until `target <= startValue`.

Once `target <= startValue`, the forward process from `startValue` to `target` cannot benefit from doubling, because doubling only increases the value. The only needed operation is decrement, repeated `startValue - target` times.

Thus the algorithm counts the minimum number of operations.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(log target)` | Each even reverse step divides `target` by `2`; odd steps make it even |
| Space | `O(1)` | Only a few integer variables are stored |

## Implementation

```python
class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        operations = 0

        while target > startValue:
            if target % 2 == 0:
                target //= 2
            else:
                target += 1

            operations += 1

        operations += startValue - target
        return operations
```

## Code Explanation

We count reverse operations:

```python
operations = 0
```

While the reverse target is still larger than `startValue`, we reduce it:

```python
while target > startValue:
```

If `target` is even, divide by `2`:

```python
if target % 2 == 0:
    target //= 2
```

If `target` is odd, add `1`:

```python
else:
    target += 1
```

Each reverse operation corresponds to one forward operation:

```python
operations += 1
```

After the loop, `target <= startValue`.

The remaining forward operations are simple decrements:

```python
operations += startValue - target
```

Then return the total:

```python
return operations
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.brokenCalc(2, 3) == 2
    assert s.brokenCalc(5, 8) == 2
    assert s.brokenCalc(3, 10) == 3
    assert s.brokenCalc(1024, 1) == 1023
    assert s.brokenCalc(1, 1) == 0
    assert s.brokenCalc(1, 1000000000) == 39

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `2, 3` | `2` | Double, then decrement |
| `5, 8` | `2` | Decrement, then double |
| `3, 10` | `3` | Standard mixed case |
| `1024, 1` | `1023` | Only decrements are useful |
| `1, 1` | `0` | Already equal |
| `1, 1000000000` | `39` | Large target checks logarithmic behavior |