# Integer Replacement
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/integer-replacement)
Canonical: https://scaleengineer.com/dsa/problems/integer-replacement
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Companies:** [Baidu](https://scaleengineer.com/companies/baidu)
---
## Problem
Given a positive integer `n`, you can apply one of the following operations:

1. If `n` is even, replace `n` with `n / 2`.
2. If `n` is odd, replace `n` with either `n + 1` or `n - 1`.

Return _the minimum number of operations needed for_ `n` _to become_ `1`.

**Example 1:**

**Input:** n = 8
**Output:** 3
**Explanation:** 8 -> 4 -> 2 -> 1

**Example 2:**

**Input:** n = 7
**Output:** 4
**Explanation:** 7 -> 8 -> 4 -> 2 -> 1
or 7 -> 6 -> 3 -> 2 -> 1

**Example 3:**

**Input:** n = 4
**Output:** 2

**Constraints:**

* `1 <= n <= 231 - 1`

# Approaches
## Brute-Force Recursion
This approach directly translates the problem's rules into a recursive function. For any given number `n`, the function determines the next step based on whether `n` is even or odd. If `n` is even, it recursively calls itself with `n / 2`. If `n` is odd, it branches, making two recursive calls for `n + 1` and `n - 1`, and proceeds with the path that yields a minimum number of future steps. This method explores all possible operation sequences to find the shortest one.
**Time:** O(2^k) where k is related to log(n) - The recursion tree branches into two every time an odd number is encountered. This leads to an exponential number of calls and re-computation of the same subproblems, making it very slow. · **Space:** O(log n) - The space complexity is determined by the maximum depth of the recursion stack. The path from `n` to 1 generally involves halving `n`, leading to a logarithmic stack depth.
**Pros:** Simple to understand and implement directly from the problem statement.
**Cons:** Extremely inefficient due to exponential time complexity.; Leads to a 'Time Limit Exceeded' error on most platforms for larger inputs.; Recomputes the same subproblems multiple times.
### Explanation
The brute-force recursive solution models the problem as a state transition graph where each number is a state. The goal is to find the shortest path from state `n` to state 1.

*   We define a recursive function, say `solve(num)`, which calculates the minimum operations for a given number `num`.
*   The base case for the recursion is when `num` is 1. In this case, 0 operations are needed, so we return 0.
*   If `num` is even, the only allowed operation is `num / 2`. The number of operations will be 1 (for the current division) plus the operations needed for `num / 2`. So, we make a recursive call `1 + solve(num / 2)`.
*   If `num` is odd, we have two choices: `num + 1` or `num - 1`. We need to find the minimum operations between these two paths. So, we recursively calculate the steps for both `num + 1` and `num - 1` and take the minimum, adding 1 for the current operation: `1 + min(solve(num + 1), solve(num - 1))`.
*   A crucial point is handling potential integer overflow. Since the input `n` can be up to `2^31 - 1`, `n + 1` can exceed the `int` range. To handle this, the recursive function should use `long` for its parameter.

```java
class Solution {
    public int integerReplacement(int n) {
        return (int) solve((long) n);
    }

    private long solve(long n) {
        if (n == 1) {
            return 0;
        }
        if (n % 2 == 0) {
            return 1 + solve(n / 2);
        } else {
            return 1 + Math.min(solve(n + 1), solve(n - 1));
        }
    }
}
```
### Algorithm
*   Define a recursive function `solve(long num)`.
*   **Base Case:** If `num == 1`, return 0, as no more operations are needed.
*   **Recursive Step (Even):** If `num` is even, the only choice is to divide by 2. Return `1 + solve(num / 2)`.
*   **Recursive Step (Odd):** If `num` is odd, we can go to `num + 1` or `num - 1`. We must explore both paths and choose the one with the minimum steps. Return `1 + min(solve(num + 1), solve(num - 1))`.
*   The initial call to the function should be `solve(n)`. Note that the function parameter should be `long` to handle the case where `n = 2^31 - 1`, as `n + 1` would overflow a standard 32-bit integer.

## Recursion with Memoization
This approach enhances the brute-force recursion by adding memoization, a top-down dynamic programming technique. It addresses the massive redundancy of the brute-force method by storing the results of subproblems in a cache (e.g., a hash map). When the function is called with a number it has seen before, it retrieves the result from the cache in constant time instead of re-computing it. This drastically reduces the number of calculations needed.
**Time:** O(log n) - With memoization, each subproblem is computed only once. The number of distinct subproblems we need to solve is on the order of `log(n)`, and each computation takes constant time. · **Space:** O(log n) - Space is required for both the recursion stack and the memoization map. The number of unique states visited and stored is proportional to the logarithm of `n`.
**Pros:** Significantly more efficient than brute-force, with a time complexity of O(log n).; Guarantees that each subproblem is solved only once.; Passes for all input constraints.
**Cons:** Requires extra space for the memoization cache.; Slightly more complex to implement than the brute-force approach.; May have higher overhead than a purely iterative solution due to recursion.
### Explanation
The main drawback of the brute-force approach is that it solves the same subproblems repeatedly. For example, in calculating the path for `n=7`, we might compute the steps for `n=4` multiple times. Memoization solves this.

We use a hash map to store the results of `solve(num)` once they are computed. The key is the number `num` and the value is the minimum operations required.

*   Before computing the result for a number `num`, we first check if it's already in our cache. If it is, we return the cached value directly.
*   If the result is not in the cache, we compute it using the same recursive logic as the brute-force approach.
*   Once the result is computed, we store it in the cache before returning it. This ensures that any future call with the same number `num` will be an O(1) lookup.
*   Again, we must use `long` for the numbers to prevent integer overflow when `n` is `Integer.MAX_VALUE`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int integerReplacement(int n) {
        Map<Long, Integer> memo = new HashMap<>();
        return (int) solve((long) n, memo);
    }

    private long solve(long n, Map<Long, Integer> memo) {
        if (n == 1) {
            return 0;
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        long result;
        if (n % 2 == 0) {
            result = 1 + solve(n / 2, memo);
        } else {
            result = 1 + Math.min(solve(n + 1, memo), solve(n - 1, memo));
        }
        memo.put(n, result);
        return result;
    }
}
```
### Algorithm
*   Create a `Map<Long, Integer>` to serve as a cache for memoization.
*   Define a recursive helper function `solve(long num, Map<Long, Integer> cache)`.
*   **Base Case:** If `num == 1`, return 0.
*   **Memoization Check:** Before any computation, check if `cache` already contains the result for `num`. If so, return the cached value.
*   **Recursive Step (Even):** If `num` is even, calculate `res = 1 + solve(num / 2, cache)`.
*   **Recursive Step (Odd):** If `num` is odd, calculate `res = 1 + min(solve(num + 1, cache), solve(num - 1, cache))`.
*   **Cache Update:** Store the computed result `res` in the cache with `num` as the key: `cache.put(num, res)`.
*   Return `res`.
*   The initial call is `solve(n, new HashMap<>())`.

## Iterative Greedy Approach with Bit Manipulation
This highly efficient approach uses an iterative, greedy strategy based on bit manipulation. The key insight is that when `n` is odd, we should choose the operation (`n+1` or `n-1`) that results in a number with the most factors of 2. This allows for the maximum number of subsequent divisions by 2 (right shifts), which reduces the number most quickly. This greedy choice works for all cases except for `n=3`, which must be handled as a special case.
**Time:** O(log n) - At each step (or every two steps for an odd number), the number `n` is roughly halved. Therefore, the number of iterations in the loop is proportional to the number of bits in `n`, which is `log(n)`. · **Space:** O(1) - This iterative approach only uses a few variables to keep track of the current number and the operation count, resulting in constant space usage.
**Pros:** Most efficient solution with O(log n) time and O(1) space.; Iterative approach avoids recursion overhead and potential stack overflow issues.; Bit manipulation provides a fast way to check the conditions.
**Cons:** The greedy logic, particularly the bit manipulation and the handling of the `n=3` edge case, can be less intuitive to derive than a straightforward recursive solution.
### Explanation
An iterative approach avoids recursion overhead and can be more efficient. The optimal strategy relies on a greedy choice at each step.

*   **If `n` is even:** The choice is forced: `n -> n / 2`. This is always optimal.
*   **If `n` is odd:** We choose between `n+1` and `n-1`. The goal is to reach a number that is divisible by 4, if possible, as this allows two divisions by 2. 
    *   If `n`'s binary representation ends in `...01` (e.g., 5, 9, 13), then `n-1` ends in `...00` (divisible by 4), while `n+1` ends in `...10`. So, `n-1` is the better choice.
    *   If `n`'s binary representation ends in `...11` (e.g., 7, 11, 15), then `n+1` ends in `...00` (divisible by 4), while `n-1` ends in `...10`. So, `n+1` is the better choice.
*   **Special Case:** The number 3 (binary `11`) is an exception. The rule suggests `3 -> 3+1=4`, leading to `3 -> 4 -> 2 -> 1` (3 steps). However, `3 -> 3-1=2` is better: `3 -> 2 -> 1` (2 steps). So, `n=3` must be handled separately.

This logic can be implemented efficiently using bitwise operations in a `while` loop.

```java
class Solution {
    public int integerReplacement(int n) {
        long num = n;
        int count = 0;
        while (num > 1) {
            count++;
            if ((num & 1) == 0) { // Even number
                num >>>= 1; // Unsigned right shift is equivalent to division by 2 for positive numbers
            } else if (num == 3 || ((num >>> 1) & 1) == 0) { // Odd, and n=3 or n's binary form ends in ...01
                num--;
            } else { // Odd, and n's binary form ends in ...11
                num++;
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize an operation `count = 0`.
*   Cast the input `n` to a `long` to handle potential overflow with `Integer.MAX_VALUE`.
*   Loop while `num > 1`.
*   In each iteration, increment the `count`.
*   **If `num` is even:** Perform a right bit shift: `num >>>= 1`.
*   **If `num` is odd:**
    *   Check for the special case `num == 3`. If so, decrement `num` (`num--`).
    *   Otherwise, check the second to last bit of `num`. This can be done with `((num >>> 1) & 1) == 0`.
    *   If the second to last bit is 0 (i.e., `num` ends in `...01`), decrement `num`. This creates a number with at least two trailing zeros.
    *   If the second to last bit is 1 (i.e., `num` ends in `...11`), increment `num`. This also creates a number with at least two trailing zeros.
*   Once the loop finishes, return `count`.

# Solutions
### Java

```java
class Solution {
public
  int integerReplacement(int n) {
    int ans = 0;
    while (n != 1) {
      if ((n & 1) == 0) {
        n >> >= 1;
      } else if (n != 3 && (n & 3) == 3) {
        ++n;
      } else {
        --n;
      }
      ++ans;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int integerReplacement(int N) {
    int ans = 0;
    long n = N;
    while (n != 1) {
      if ((n & 1) == 0)
        n >>= 1;
      else if (n != 3 && (n & 3) == 3)
        ++n;
      else
        --n;
      ++ans;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def integerReplacement(self, n: int) -> int: ans = 0 while n != 1: if (n & 1) == 0: n >>= 1 elif n != 3 and (n & 3) == 3: n += 1 else: n -= 1 ans += 1 return ans

```