Integer Replacement: Greedy Bit Manipulation

Integer Replacement is LeetCode 397, rated Medium. You are given a positive integer n and need to reach 1 in the fewest possible operations. If n is even, you divide by 2. If n is odd, you can either add 1 or subtract 1. The challenge is knowing which choice to make for odd numbers so you minimize the total number of steps.

The problem

Given a positive integer n, return the minimum number of replacements needed to transform n into 1. In each step you can apply one of three operations:

• If n is even, replace n with n / 2.
• If n is odd, replace n with n + 1 or n - 1.

Input:  n = 8
Output: 3
# 8 -> 4 -> 2 -> 1

Input:  n = 7
Output: 4
# 7 -> 8 -> 4 -> 2 -> 1

Input:  n = 4
Output: 2
# 4 -> 2 -> 1

For n = 7, it might seem like subtracting 1 to get 6 is a good idea (since 6 is closer to 1). But 7 to 8 to 4 to 2 to 1 takes 4 steps, while 7 to 6 to 3 branches further. The right choice depends on the bit pattern, not the magnitude.

Why greedy bit analysis works

When n is even, there is no decision to make. You divide by 2, which is the same as right-shifting the binary representation by one bit.

When n is odd, both n + 1 and n - 1 produce an even number. The question is which one leads to more consecutive divisions by 2. The answer lives in the last two bits of n:

• If n % 4 == 1 (binary ends in 01), subtracting 1 gives a number ending in 00, which means at least two consecutive divisions. Adding 1 would give a number ending in 10, allowing only one division before hitting another odd number.
• If n % 4 == 3 (binary ends in 11), adding 1 gives a number ending in 00, which allows at least two consecutive divisions. Subtracting 1 would give a number ending in 10, allowing only one.

There is one exception: when n == 3, the rule says to add 1 (since 3 % 4 == 3), but going 3 to 4 to 2 to 1 is 3 steps, while 3 to 2 to 1 is only 2 steps. So n = 3 is a special case where you subtract instead.

Step-by-step walkthrough

Let's trace through n = 7 using the greedy bit rule. At each step, we check whether n is even or odd, and for odd numbers we use the n % 4 test to pick the better direction.

A few observations:

• Step 1 is the critical decision. For n = 7, we have 7 % 4 == 3, so the rule says to add 1. This produces 8, a power of 2, which collapses to 1 in just three more divisions.
• Had we subtracted instead, we would get 6, then 3. At n = 3 (the special case), we subtract to get 2, then 1. That path is 7, 6, 3, 2, 1 for 4 steps. Same count here, but the greedy rule generalizes correctly for larger numbers.
• Every even step is automatic. No decision needed, just divide.

The code

Here is the Python solution for LeetCode 397, Integer Replacement:

def integer_replacement(n: int) -> int:
    count = 0
    while n != 1:
        if n % 2 == 0:
            n //= 2
        elif n == 3 or n % 4 == 1:
            n -= 1
        else:
            n += 1
        count += 1
    return count

Let's break down each branch:

• Even: n //= 2 performs integer division. This is the only option for even numbers and corresponds to a right bit shift.
• Odd with n % 4 == 1: The last two bits are 01. Subtracting 1 gives 00 at the end, creating two or more trailing zeros for consecutive divisions.
• Odd with n % 4 == 3: The last two bits are 11. Adding 1 flips them to 00 (with a carry), creating trailing zeros. This is better than subtracting, which would give 10.
• Special case n == 3: Even though 3 % 4 == 3, subtracting is better because 3 to 2 to 1 is only 2 steps, while 3 to 4 to 2 to 1 is 3 steps. The n == 3 check in the elif catches this before the general n % 4 == 3 rule in the else branch.

Complexity analysis

Time: O(log n). Each iteration either divides n by 2 (halving it) or adjusts it by 1 before the next division. The number of bits in n decreases steadily, so the loop runs at most about 2 * log2(n) times, which is O(log n).

Space: O(1). We only use a counter variable and modify n in place. No recursion, no stack, no auxiliary data structures.

This is optimal. You must examine every bit of n at least once to decide what to do with it, and the greedy approach does exactly that with constant work per bit.

The building blocks

This problem is built on one core pattern: greedy bit-level decision making.

Greedy trailing-bit analysis

The pattern is: when you have a choice that affects a binary number, look at the last few bits to make the locally optimal decision. For Integer Replacement, looking at the last two bits (n % 4) tells you exactly which direction minimizes future operations. The local greedy choice turns out to be globally optimal because each decision only affects the trailing bits, and the higher bits are handled independently by future iterations.

This same trailing-bit analysis pattern appears in:

• Power of Two (LeetCode 231): Check if exactly one bit is set using n & (n - 1) == 0.
• Counting Bits (LeetCode 338): Use the relationship between n and n >> 1 to build up bit counts dynamically.
• Bitwise AND of Numbers Range (LeetCode 201): Find the common prefix of two binary numbers by stripping trailing bits.
• Number of 1 Bits (LeetCode 191): Count set bits using n & (n - 1) to clear the lowest set bit each time.

Edge cases

Before submitting, verify your solution handles:

• n = 1: Already at the goal. The answer is 0. The while loop never executes.
• n = 2: One step: 2 / 2 = 1. The answer is 1.
• n = 3: Special case. The greedy rule would say n + 1 (since 3 % 4 == 3), but 3 -> 2 -> 1 in 2 steps beats 3 -> 4 -> 2 -> 1 in 3 steps.
• Large powers of 2: n = 2^31 should return 31. Each step just divides by 2.
• n = 2^31 - 1 (all bits set): This is a large odd number. The algorithm should handle it without overflow issues in Python (which has arbitrary precision integers).

From understanding to recall

You now understand the greedy bit manipulation approach. You see why n % 4 determines the optimal choice for odd numbers, and why n = 3 is a special case. But will you remember the exact branching logic during an interview?

The details that slip away under pressure are subtle. Is the condition n % 4 == 1 for subtracting or adding? Does the special case apply to n = 3 or n = 1? Should you check n == 3 before or after the n % 4 test? These are small details, but getting any one of them wrong changes the answer.

Spaced repetition locks in the exact branching order. You write the while loop, the three-way branch, and the n = 3 guard from scratch at increasing intervals. After a few repetitions, the elif n == 3 or n % 4 == 1 line comes out automatically, and you never confuse the direction of the special case again.

Related posts

• Power of Two - bit manipulation for checking powers
• Counting Bits - dynamic programming with bit patterns
• Number of 1 Bits - Hamming weight and bit counting

CodeBricks breaks the Integer Replacement greedy pattern into its reusable building blocks and drills them with spaced repetition. You type the solution from scratch each time, so when LeetCode 397 or any bit-level greedy problem shows up in an interview, the branching logic flows without hesitation.