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.
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.
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.
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.
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 | 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 | — |
| 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. |
LeetCode 397. Integer Replacement • Happy Coding • 3,427 views views
Watch 9 more video solutions →Practice Integer Replacement with our built-in code editor and test cases.
Practice on FleetCode