Computer Science
Updated 18 days ago | GitHub

Integer Replacement

Problem Highlights

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • What are the constraints?

    • 1 <= n <= 2^31 - 1

  • How can we handle odd numbers?

    • There is subtle trick in this problem that allows us to choose either x-1 or x+1 when x is odd. Say x is 7. Then x-1 = 6 and x+1 = 8. 6/2 = 3 and 8/2=4. Now this is consistent - either (x-1)/2 is even or (x+1)/2 is even. And we want to pick the path that leads us to an even number to reach our goal fastest. One exception is x = 3 where both (x-1)/2 is odd or (x+1)/2 is even. For this case, use x-1 which takes us to 2.
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

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

At each step there is at most one real choice to make: an even number must be halved, and an odd number can only become n - 1 or n + 1. That is a clue to use a greedy strategy — if we can prove which of the two options is always at least as good, we never need to explore both branches. The insight from the U-nderstand section gives us that proof: for an odd n, exactly one of (n - 1) / 2 and (n + 1) / 2 is even, and steering toward the even result lets us divide by 2 again immediately. The one exception is n = 3, where subtracting reaches 1 in two steps while adding would take three. Checking whether a number is even and picking the right neighbor are both cheap bit operations (n & 1, or (n + 1) % 4 == 0 in the Java version), so the whole solution is a simple greedy loop with bit manipulation — no recursion or memoization table is needed.

⚠️ Common Mistakes

  • Trying both n - 1 and n + 1 on every odd number with plain recursion re-solves the same subproblems exponentially many times; if you do take the brute-force recursive route, it needs memoization to stay fast. The greedy rule above avoids the branching entirely.
  • Forgetting the n = 3 exception: (3 + 1) / 2 = 2 is even, so the “steer toward even” rule alone would choose n + 1 and take 3 steps, but 3 -> 2 -> 1 only takes 2.
  • In languages with fixed-width integers, n + 1 overflows when n is the maximum 32-bit integer (the Java solution special-cases Integer.MAX_VALUE for exactly this reason).

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

1) if the number is even divide it by 2 and continue
2) if the number is odd take the two possible numbers and divide it by 2 and use the one that results in an even number since odd adds an extra step.
3) When the resultant num when divided by 2 in step 2 is 1 use the smallest num.

4: I-mplement

Implement the code to solve the algorithm.

class Solution(object):
    def integerReplacement(self, n):
        if n <= 1:
            return 0
        level = 0
        while n != 1:
            if n & 1 == 0:
                n, level = n // 2, level + 1
            elif n == 3:
                n, level = n-1, level + 1
            else:
                if (n-1) // 2 & 1 == 0:
                    n, level = n-1, level + 1
                else:
                    n, level = n+1, level + 1                    
        return level   

public int integerReplacement(int n) {
    if (n == Integer.MAX_VALUE) return 32; //n = 2^31-1;
    int count = 0;
    while (n > 1){
        if (n % 2 == 0) n  /= 2;
        else{
            if ( (n + 1) % 4 == 0 && (n - 1 != 2) ) n++;
            else n--;
        }
        count++;
    }
    return count;
}

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

  • Trace through your code with an input to check for the expected output
  • Catch possible edge cases and off-by-one errors

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

  • Time Complexity: O(Logn)
  • Space Complexity: O(1), both shown solutions are iterative and only use a few scalar variables