Problem Description

The Integer Replacement problem asks: Given a positive integer n, return the minimum number of operations needed to transform n into 1.
In each operation, you may:

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

• 1 <= n <= 231 - 1

Thought Process

At first glance, this problem appears to be a simple recursive challenge: keep halving when even, and when odd, try both incrementing and decrementing, picking the path with the fewest steps.

However, a brute-force approach will quickly become inefficient for large n due to repeated calculations and the exponential number of paths when n is odd.

To optimize, we notice:

• When n is even, there is only one choice: halve it. This is always optimal.
• When n is odd, we can either increment or decrement. Choosing the better option at each step can significantly reduce the number of operations.
• We can use memoization to avoid recomputation, or analyze bit patterns to make greedy choices.

Solution Approach

Let's break down the solution step-by-step:

1. Recursive Approach:
   • If n is even, the optimal move is always n / 2.
   • If n is odd, try both n + 1 and n - 1, and take the minimum result.
2. Memoization:
   • Store results of subproblems in a hash map or cache to avoid redundant work.
3. Greedy/Bit Manipulation Optimization:
   • For odd n, check the two least significant bits. If n == 3 or n % 4 == 1, decrementing is better; otherwise, incrementing is more optimal. This is because we want to maximize the number of trailing zeros after the operation, allowing more divisions by 2.

The recursive + memoized approach is easier to understand and implement, while the bit manipulation greedy approach is faster and more space-efficient.

Example Walkthrough

Let's trace the process with n = 7:

1. 7 is odd: choices are 6 or 8.
2. Try 7 - 1 = 6:
   • 6 is even: 6 / 2 = 3
   • 3 is odd: choices are 2 or 4
   • Try 3 - 1 = 2: 2 / 2 = 1 (reached!)
   • Steps for this path: 7 → 6 → 3 → 2 → 1 (4 steps)
3. Try 7 + 1 = 8:
   • 8 / 2 = 4
   • 4 / 2 = 2
   • 2 / 2 = 1 (reached!)
   • Steps for this path: 7 → 8 → 4 → 2 → 1 (4 steps)
4. Both paths take 4 steps, so the answer is 4.

For larger numbers, the greedy approach helps avoid unnecessary detours by always picking the path that leads to more trailing zeros (more consecutive divisions by 2).

Time and Space Complexity

Brute-Force Approach:

• Time Complexity: Exponential in the number of odd steps, since each odd number branches into two recursive calls.
• Space Complexity: Proportional to the recursion depth (O(log n)), but can be much larger due to repeated subproblems.

• Time Complexity: O(log n), since each division by 2 reduces n quickly, and memoization prevents redundant calculations.
• Space Complexity: O(log n) for the recursion stack and memoization storage.

• Time Complexity: O(log n), as each step halves the number or makes a single increment/decrement.
• Space Complexity: O(1), since it can be implemented iteratively without extra storage.

Summary

The Integer Replacement problem is a classic example of recursive optimization. By carefully analyzing the operations and leveraging memoization or bit manipulation, we can transform a naive exponential solution into a highly efficient one. The key insight is to minimize the number of steps for odd numbers by choosing the operation that allows more divisions by 2 in the future, and to avoid recomputation by caching results. This approach ensures the solution is both elegant and performant even for very large inputs.

Code Implementation

class Solution:
    def integerReplacement(self, n: int) -> int:
        memo = {}
        def helper(x):
            if x == 1:
                return 0
            if x in memo:
                return memo[x]
            if x % 2 == 0:
                memo[x] = 1 + helper(x // 2)
            else:
                memo[x] = 1 + min(helper(x + 1), helper(x - 1))
            return memo[x]
        return helper(n)
      

class Solution {
public:
    int integerReplacement(int n) {
        unordered_map memo;
        function helper = [&](long long x) {
            if (x == 1) return 0;
            if (memo.count(x)) return memo[x];
            if (x % 2 == 0) {
                memo[x] = 1 + helper(x / 2);
            } else {
                memo[x] = 1 + min(helper(x + 1), helper(x - 1));
            }
            return memo[x];
        };
        return helper((long long)n);
    }
};
      

class Solution {
    private Map memo = new HashMap<>();
    public int integerReplacement(int n) {
        return helper((long)n);
    }
    private int helper(long x) {
        if (x == 1) return 0;
        if (memo.containsKey(x)) return memo.get(x);
        int res;
        if (x % 2 == 0) {
            res = 1 + helper(x / 2);
        } else {
            res = 1 + Math.min(helper(x + 1), helper(x - 1));
        }
        memo.put(x, res);
        return res;
    }
}
      

var integerReplacement = function(n) {
    const memo = new Map();
    function helper(x) {
        if (x === 1) return 0;
        if (memo.has(x)) return memo.get(x);
        let res;
        if (x % 2 === 0) {
            res = 1 + helper(x / 2);
        } else {
            res = 1 + Math.min(helper(x + 1), helper(x - 1));
        }
        memo.set(x, res);
        return res;
    }
    return helper(n);
};