Integer Replacement - Solution & Explanation
Problem Statement
Given a positive integer n, you can apply one of the following operations:
- If
nis even, replacenwithn / 2. - If
nis odd, replacenwith eithern + 1orn - 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
Approach Overview
Problem 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 1: Greedy Approach with Bit Manipulation
The greedy approach involves observing the binary representation of numbers and making decisions on whether to increment or decrement based on the number of trailing zeros. If even, always divide by 2. If odd, decide between incrementing or decrementing based on the result that gives fewer operations.
This C solution iteratively evaluates n. If n is even, it quickly halves it. For odd n, it looks at the subsequent two bits (using n & 2) to determine if incrementing or decrementing results in more trailing zeros. Special care is taken for n = 3 since reducing to 1 is optimal by decrement.
Complexity
Time Complexity: O(log n), since we reduce the problem size approximately by half each time with even numbers.
Space Complexity: O(1), only constant extra space is needed.
Approach 2: Recursive Approach with Memoization
The recursive approach leverages memoization to store previously computed results, avoiding redundant calculations. The transition involves conditional checks for even and odd numbers and memoizes solutions to subproblems, efficiently calculating the minimal operations.
In this C solution, memoization is employed to cache solutions to subproblems within the array `dp`. The recursive `helper` function is invoked with a decision pattern for both even and odd scenarios, dynamically avoiding repeat calculations by memorizing the already computed results.
Complexity
Time Complexity: O(log n), as recursive calls reduce the problem size significantly.
Space Complexity: O(n), due to caching results in the dp array storing results from 0 to n.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Bit Manipulation | Time Complexity: O(log n), since we reduce the problem size approximately by half each time with even numbers. |
| Recursive Approach with Memoization | Time Complexity: O(log n), as recursive calls reduce the problem size significantly. |
| Default Approach | — |
Detailed Complexity Analysis
| 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. |
Video Solution
LeetCode 397. Integer Replacement • Happy Coding • 3,525 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Integer Replacement easy or hard?
Integer Replacement Python/Java solution
How to solve Integer Replacement in O(log n)?
What is the best approach for Integer Replacement?
Is Integer Replacement asked at Google/Amazon/Meta?
What data structure is used in Integer Replacement?
What is the time complexity of Integer Replacement?
Ready to solve this problem?
Practice Integer Replacement with our built-in code editor and test cases.
Practice on FleetCode