Watch 10 video solutions for Integer Replacement, a medium level problem involving Dynamic Programming, Greedy, Bit Manipulation. This walkthrough by NeetCode has 599,364 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a positive integer n, you can apply one of the following operations:
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 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 - 1Problem Overview: Given a positive integer n, reduce it to 1 using the minimum number of operations. If n is even you can divide by 2, and if it is odd you can either increment or decrement by 1. The challenge is choosing the correct direction for odd numbers to minimize the total number of steps.
Approach 1: Recursive Approach with Memoization (Time: O(log n), Space: O(log n))
This approach models the problem as a recursive decision tree. For every odd number n, you evaluate both possibilities: n + 1 and n - 1. For even numbers, the decision is deterministic because dividing by two is always optimal. Memoization stores previously computed results in a hash map so repeated states are not recomputed. Since the value roughly halves whenever it becomes even, the recursion depth grows proportional to log n. This method is straightforward to reason about and demonstrates classic dynamic programming with memoization, but it still explores both branches for odd values before caching results.
Approach 2: Greedy with Bit Manipulation (Time: O(log n), Space: O(1))
The optimal approach relies on binary patterns. When n is even, right shifting (n / 2) removes a trailing zero bit, which always reduces the number efficiently. When n is odd, the decision between n + 1 and n - 1 depends on the last two bits. If n % 4 == 1, decrementing produces more trailing zeros and speeds up future divisions. If n % 4 == 3, incrementing is better because it often collapses a sequence of ones in binary. The only exception is n == 3, where decrementing reaches the optimal path faster. This strategy uses simple bit checks and avoids recursion entirely, making it a clean example of combining greedy algorithms with bit manipulation.
Recommended for interviews: Interviewers usually expect the greedy bit manipulation insight because it reduces the search space and achieves O(log n) time with constant space. Starting with the recursive memoized solution shows correct problem modeling and understanding of dynamic programming. Moving to the greedy bit-based rule demonstrates deeper optimization and familiarity with binary reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(log n) | O(log n) | Good for understanding the decision tree and demonstrating dynamic programming techniques. |
| Greedy with Bit Manipulation | O(log n) | O(1) | Preferred optimal solution for interviews and production due to constant space and simple bit checks. |