Scale Engineer

Integer Replacement

Med
#0384Time: 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.1 company
Patterns
Dynamic ProgrammingGreedyBit ManipulationMemoization
Companies
Baidu

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.
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));        }    }}

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem