# LeetCode 397: Integer Replacement

## Problem Restatement

We are given a positive integer `n`.

We need to turn `n` into `1` using the fewest operations.

The allowed operations are:

| Case | Operation |
|---|---|
| `n` is even | Replace `n` with `n / 2` |
| `n` is odd | Replace `n` with either `n + 1` or `n - 1` |

Return the minimum number of operations needed.

For example:

```python
n = 8
```

The best path is:

```text
8 -> 4 -> 2 -> 1
```

So the answer is `3`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A positive integer `n` |
| Output | Minimum number of operations to reach `1` |
| Constraint | `1 <= n <= 2^31 - 1` |

Example function shape:

```python
def integerReplacement(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 8
```

Since `8` is even:

```text
8 -> 4 -> 2 -> 1
```

The answer is:

```python
3
```

Example 2:

```python
n = 7
```

There are two natural choices:

```text
7 -> 8 -> 4 -> 2 -> 1
```

This takes `4` operations.

Or:

```text
7 -> 6 -> 3 -> 2 -> 1
```

This also takes `4` operations.

So the answer is:

```python
4
```

Example 3:

```python
n = 4
```

The path is:

```text
4 -> 2 -> 1
```

The answer is:

```python
2
```

## First Thought: Recursion With Memoization

A direct way is to define:

```python
dp(x)
```

as the minimum number of operations needed to reduce `x` to `1`.

If `x == 1`, the answer is `0`.

If `x` is even:

```python
dp(x) = 1 + dp(x // 2)
```

If `x` is odd:

```python
dp(x) = 1 + min(dp(x - 1), dp(x + 1))
```

This is easy to reason about.

```python
from functools import cache

class Solution:
    def integerReplacement(self, n: int) -> int:
        @cache
        def dp(x: int) -> int:
            if x == 1:
                return 0

            if x % 2 == 0:
                return 1 + dp(x // 2)

            return 1 + min(dp(x - 1), dp(x + 1))

        return dp(n)
```

This works in Python, but there is an even simpler iterative greedy solution.

## Key Insight

Even numbers have no choice. We should always divide by `2`.

The only decision happens when `n` is odd.

For an odd number, either `n - 1` or `n + 1` is even. After that, we can divide by `2`.

We want to create more trailing zero bits, because trailing zeros allow repeated division by `2`.

Look at the last two bits.

If an odd number ends in binary `01`, subtracting `1` creates a number ending in `00`.

Example:

```text
9  = 1001
8  = 1000
```

So for numbers ending in `01`, decrement is good.

If an odd number ends in binary `11`, adding `1` often creates more trailing zeros.

Example:

```text
15 = 1111
16 = 10000
```

So for numbers ending in `11`, increment is usually good.

There is one important exception:

```text
3 -> 2 -> 1
```

This takes `2` operations.

But:

```text
3 -> 4 -> 2 -> 1
```

takes `3` operations.

So when `n == 3`, we subtract.

## Algorithm

Initialize:

```python
steps = 0
```

While `n != 1`:

1. If `n` is even, divide by `2`.
2. Otherwise, if `n == 3`, subtract `1`.
3. Otherwise, if the last two bits are `11`, add `1`.
4. Otherwise, subtract `1`.
5. Increase `steps`.

The bit checks are:

```python
n & 1
```

to check odd or even, and:

```python
n & 3
```

to read the last two bits.

If:

```python
n & 3 == 3
```

then `n` ends in binary `11`.

## Correctness

When `n` is even, the only allowed operation is `n / 2`, so the algorithm must perform it.

When `n` is odd, both `n - 1` and `n + 1` are even. The next useful operation will divide by `2`.

For odd numbers ending in binary `01`, subtracting `1` creates a multiple of `4`, while adding `1` creates a number only divisible by `2`. Creating more factors of `2` cannot hurt, because division by `2` is the fastest way to reduce the number.

For odd numbers ending in binary `11`, adding `1` creates a multiple of `4`, except for the special case `3`. This usually gives more immediate divisions by `2` than subtracting `1`.

The case `n = 3` must subtract because:

```text
3 -> 2 -> 1
```

is shorter than:

```text
3 -> 4 -> 2 -> 1
```

So the greedy choice always chooses the branch that creates the better even number for future halving, with the required exception for `3`.

Therefore the algorithm reaches `1` in the minimum number of operations.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | Every one or two operations reduces the bit length or creates more division by `2` |
| Space | `O(1)` | Only `n` and `steps` are stored |

## Implementation

```python
class Solution:
    def integerReplacement(self, n: int) -> int:
        steps = 0

        while n != 1:
            if n % 2 == 0:
                n //= 2
            elif n == 3 or n % 4 == 1:
                n -= 1
            else:
                n += 1

            steps += 1

        return steps
```

## Bitwise Implementation

The same logic can be written with bit operations:

```python
class Solution:
    def integerReplacement(self, n: int) -> int:
        steps = 0

        while n != 1:
            if (n & 1) == 0:
                n >>= 1
            elif n == 3 or (n & 3) == 1:
                n -= 1
            else:
                n += 1

            steps += 1

        return steps
```

## Code Explanation

We count operations:

```python
steps = 0
```

The loop stops when `n` becomes `1`:

```python
while n != 1:
```

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

```python
if (n & 1) == 0:
    n >>= 1
```

If `n` is odd and equal to `3`, subtract:

```python
elif n == 3:
    n -= 1
```

If the last two bits are `01`, subtract:

```python
elif (n & 3) == 1:
    n -= 1
```

Otherwise the last two bits are `11`, so add:

```python
else:
    n += 1
```

Each loop performs one operation:

```python
steps += 1
```

Finally:

```python
return steps
```

## Testing

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

    assert s.integerReplacement(1) == 0
    assert s.integerReplacement(2) == 1
    assert s.integerReplacement(3) == 2
    assert s.integerReplacement(4) == 2
    assert s.integerReplacement(7) == 4
    assert s.integerReplacement(8) == 3
    assert s.integerReplacement(15) == 5
    assert s.integerReplacement(16) == 4
    assert s.integerReplacement(2147483647) == 32

    print("all tests passed")

test_solution()
```

Test meaning:

| Test | Why |
|---|---|
| `1` | Already finished |
| `2` | One division |
| `3` | Special case where subtracting is better |
| `4` | Power of two |
| `7` | Both directions have optimal length |
| `8` | Main even example |
| `15` | Ends in binary `11`, increment is useful |
| `16` | Power of two boundary |
| `2147483647` | Largest 32-bit signed input |