Integer Replacement Solution in Java

Explore More Solutions:

Problem Description

Ah, the classic Integer Replacement problem! Imagine you have a number, let’s say it’s your age (don’t worry, we won’t tell anyone). Now, you want to reduce this number to 1, but there’s a catch! You can only do it by either dividing it by 2 (if it’s even) or adding or subtracting 1 (if it’s odd). It’s like trying to lose weight by either going to the gym (dividing by 2) or just skipping dessert (adding or subtracting 1).

The goal is to find the minimum number of operations required to turn your age into 1. So, if you’re 3 years old, you can just subtract 1 to become 2, and then divide by 2 to reach 1. Easy peasy, right? But if you’re 7, you might have to think a bit more.

Let’s dive into the code solution!


class Solution {
  public int integerReplacement(long n) {
    int ans = 0;

    for (; n > 1; ++ans)
      if (n % 2 == 0) // `n` ends in 0.
        n >>= 1;
      else if (n == 3 || (n >> 1 & 1) == 0) // `n` = 3 or ends in 0b01.
        --n;
      else // `n` ends in 0b11.
        ++n;

    return ans;
  }
}

Approach Explanation

The approach here is quite straightforward. We use a loop that continues until n is greater than 1. If n is even, we simply divide it by 2 (using a right shift operation for efficiency). If n is odd, we have two scenarios: if n is 3 or if the next number (n-1) is even, we subtract 1. Otherwise, we add 1. This way, we minimize the number of operations needed to reach 1.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(log n)
Space Complexity	O(1)

Real-World Example

Think of it like trying to get to the top of a staircase. If you can take two steps at a time (dividing by 2), you’ll get there faster. But if you’re stuck on an odd step, you might have to take a single step up or down to get back on track. The Integer Replacement problem is just like that—finding the quickest way to reach the top (or in this case, 1).