LeetCode 397: Integer Replacement

Problem Restatement

We are given a positive integer n.

We need to turn n into 1 using the fewest operations.

The allowed operations are:

Return the minimum number of operations needed.

For example:

n = 8

The best path is:

8 -> 4 -> 2 -> 1

So the answer is 3.

Input and Output

Example function shape:

def integerReplacement(n: int) -> int:
    ...

Examples

Example 1:

n = 8

Since 8 is even:

8 -> 4 -> 2 -> 1

The answer is:

3

Example 2:

n = 7

There are two natural choices:

7 -> 8 -> 4 -> 2 -> 1

This takes 4 operations.

Or:

7 -> 6 -> 3 -> 2 -> 1

This also takes 4 operations.

So the answer is:

4

Example 3:

n = 4

The path is:

4 -> 2 -> 1

The answer is:

2

First Thought: Recursion With Memoization

A direct way is to define:

dp(x)

as the minimum number of operations needed to reduce x to 1.

If x == 1, the answer is 0.

If x is even:

dp(x) = 1 + dp(x // 2)

If x is odd:

dp(x) = 1 + min(dp(x - 1), dp(x + 1))

This is easy to reason about.

from functools import cache

class Solution:
    def integerReplacement(self, n: int) -> int:
        @cache
        def dp(x: int) -> int:
            if x == 1:
                return 0

            if x % 2 == 0:
                return 1 + dp(x // 2)

            return 1 + min(dp(x - 1), dp(x + 1))

        return dp(n)

This works in Python, but there is an even simpler iterative greedy solution.

Key Insight

Even numbers have no choice. We should always divide by 2.

The only decision happens when n is odd.

For an odd number, either n - 1 or n + 1 is even. After that, we can divide by 2.

We want to create more trailing zero bits, because trailing zeros allow repeated division by 2.

Look at the last two bits.

If an odd number ends in binary 01, subtracting 1 creates a number ending in 00.

Example:

9  = 1001
8  = 1000

So for numbers ending in 01, decrement is good.

If an odd number ends in binary 11, adding 1 often creates more trailing zeros.

Example:

15 = 1111
16 = 10000

So for numbers ending in 11, increment is usually good.

There is one important exception:

3 -> 2 -> 1

This takes 2 operations.

But:

3 -> 4 -> 2 -> 1

takes 3 operations.

So when n == 3, we subtract.

Algorithm

Initialize:

steps = 0

While n != 1:

1. If n is even, divide by 2.
2. Otherwise, if n == 3, subtract 1.
3. Otherwise, if the last two bits are 11, add 1.
4. Otherwise, subtract 1.
5. Increase steps.

The bit checks are:

n & 1

to check odd or even, and:

n & 3

to read the last two bits.

If:

n & 3 == 3

then n ends in binary 11.

Correctness

When n is even, the only allowed operation is n / 2, so the algorithm must perform it.

When n is odd, both n - 1 and n + 1 are even. The next useful operation will divide by 2.

For odd numbers ending in binary 01, subtracting 1 creates a multiple of 4, while adding 1 creates a number only divisible by 2. Creating more factors of 2 cannot hurt, because division by 2 is the fastest way to reduce the number.

For odd numbers ending in binary 11, adding 1 creates a multiple of 4, except for the special case 3. This usually gives more immediate divisions by 2 than subtracting 1.

The case n = 3 must subtract because:

3 -> 2 -> 1

is shorter than:

3 -> 4 -> 2 -> 1

So the greedy choice always chooses the branch that creates the better even number for future halving, with the required exception for 3.

Therefore the algorithm reaches 1 in the minimum number of operations.

Complexity

Implementation

class Solution:
    def integerReplacement(self, n: int) -> int:
        steps = 0

        while n != 1:
            if n % 2 == 0:
                n //= 2
            elif n == 3 or n % 4 == 1:
                n -= 1
            else:
                n += 1

            steps += 1

        return steps

Bitwise Implementation

The same logic can be written with bit operations:

class Solution:
    def integerReplacement(self, n: int) -> int:
        steps = 0

        while n != 1:
            if (n & 1) == 0:
                n >>= 1
            elif n == 3 or (n & 3) == 1:
                n -= 1
            else:
                n += 1

            steps += 1

        return steps

Code Explanation

We count operations:

steps = 0

The loop stops when n becomes 1:

while n != 1:

If n is even, divide by 2:

if (n & 1) == 0:
    n >>= 1

If n is odd and equal to 3, subtract:

elif n == 3:
    n -= 1

If the last two bits are 01, subtract:

elif (n & 3) == 1:
    n -= 1

Otherwise the last two bits are 11, so add:

else:
    n += 1

Each loop performs one operation:

steps += 1

Finally:

return steps

Testing

def test_solution():
    s = Solution()

    assert s.integerReplacement(1) == 0
    assert s.integerReplacement(2) == 1
    assert s.integerReplacement(3) == 2
    assert s.integerReplacement(4) == 2
    assert s.integerReplacement(7) == 4
    assert s.integerReplacement(8) == 3
    assert s.integerReplacement(15) == 5
    assert s.integerReplacement(16) == 4
    assert s.integerReplacement(2147483647) == 32

    print("all tests passed")

test_solution()

Test meaning: