Integer Replacement

medium math greedy bit manipulation

Problem

Given a positive integer n, in one operation you may either replace n with n/2 (if even) or with n+1 / n−1 (if odd). Return the minimum number of operations to reach 1.

Inputn = 7

Output4

7 → 8 → 4 → 2 → 1. Picking +1 was better than −1 because it created a longer run of trailing zeros.

def integer_replacement(n):
    steps = 0
    while n != 1:
        if n % 2 == 0:
            n //= 2
        elif n == 3 or (n & 2) == 0:
            n -= 1
        else:
            n += 1
        steps += 1
    return steps

function integerReplacement(n) {
  let steps = 0;
  while (n !== 1) {
    if (n % 2 === 0) n = n / 2;
    else if (n === 3 || (n & 2) === 0) n -= 1;
    else n += 1;
    steps++;
  }
  return steps;
}

class Solution {
    public int integerReplacement(int n) {
        int steps = 0;
        long m = n;
        while (m != 1) {
            if ((m & 1) == 0) m /= 2;
            else if (m == 3 || (m & 2) == 0) m -= 1;
            else m += 1;
            steps++;
        }
        return steps;
    }
}

int integerReplacement(int n) {
    int steps = 0;
    long long m = n;
    while (m != 1) {
        if ((m & 1) == 0) m /= 2;
        else if (m == 3 || (m & 2) == 0) m -= 1;
        else m += 1;
        steps++;
    }
    return steps;
}

Explanation

We want to shrink n down to 1 in as few steps as possible. The big idea is that halving is the fastest move, so we want to set ourselves up to halve as often as we can — this is a greedy, bit-aware strategy.

If n is even, halving is always best, so we just do n /= 2. The interesting case is when n is odd: we must choose between n - 1 and n + 1, and we want the choice that produces more trailing zero bits (so future halvings go further).

The condition n == 3 || (n & 2) == 0 decides this. Looking at the last two bits: if they are 01 (so n & 2 is 0), subtracting 1 lands on a clean even number, so we do n - 1. Otherwise the bits are 11, and adding 1 carries through to create a longer run of zeros, so we do n + 1. The number 3 is a special case where subtracting is better.

Example: n = 7 (binary 111). It is odd and ends in 11, so we add 1 to get 8. Then 8 → 4 → 2 → 1 by halving. That is 4 steps, which is optimal; choosing 7 → 6 first would have taken longer.

Because we roughly halve the number on most steps, the total number of operations is about O(log n).

Time: O(log n) Space: O(1)