LeetCode Problem 397

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Greedy, Bit Manipulation, Memoization

Solution

LeetCode 397 - Integer Replacement

Problem Understanding

The problem gives us a positive integer n and asks for the minimum number of operations required to transform it into 1.

At every step, we are allowed to apply one of two rules:

• If the number is even, we must divide it by 2
• If the number is odd, we may either increment it by 1 or decrement it by 1

The goal is to determine the smallest possible number of operations needed to eventually reach 1.

The input is a single integer n, and the output is an integer representing the minimum operation count.

The constraint is especially important:

1 <= n <= 2^31 - 1

This means the input can be as large as 2147483647, which is the maximum signed 32-bit integer. Because of this, any brute-force search that explores too many repeated states will become infeasible. The solution must carefully avoid exponential branching.

One subtle detail is that odd numbers introduce two possible choices, n + 1 and n - 1. A naive implementation might recursively explore both possibilities for every odd number, which quickly becomes expensive.

Another important edge case is the maximum integer value 2^31 - 1. In languages with fixed-width integers, adding 1 may overflow. This is particularly relevant in Go and many other compiled languages.

The problem guarantees that the input is always positive, so we never need to handle zero or negative values.

Approaches

Brute Force Approach

The most straightforward solution is to use recursive backtracking.

For every number:

• If it is even, recursively solve for n / 2

• If it is odd, recursively compute both:

• steps for n + 1

• steps for n - 1

• Take the minimum result

This guarantees correctness because it explores every possible sequence of operations and chooses the shortest one.

However, this approach is extremely inefficient because many states are recomputed repeatedly. For example, different recursive paths may eventually reach the same intermediate number. Without caching, the recursion tree grows exponentially.

For large values near 2^31 - 1, the brute-force solution becomes far too slow.

Optimal Approach

The key insight is that for odd numbers, we do not actually need to explore both branches blindly.

We want to make the number divisible by higher powers of two as quickly as possible, because dividing by two rapidly shrinks the number.

For an odd number:

• If subtracting 1 produces more trailing zero bits, it is usually better
• If adding 1 produces more trailing zero bits, it is usually better

This leads to the greedy bit-manipulation observation:

• If n == 3 or the second least significant bit is 0, use n - 1
• Otherwise use n + 1

In binary:

• Numbers ending in 01 benefit from subtracting
• Numbers ending in 11 benefit from adding

Examples:

5  = 101
5 - 1 = 100   -> divisible by 4

7  = 111
7 + 1 = 1000  -> divisible by 8

This strategy minimizes the number of future operations.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^k)	O(k)	Explores both choices for every odd number
Optimal	O(log n)	O(1)	Greedy bit manipulation reduces the number efficiently

Here, k represents the number of recursive branching decisions.

Algorithm Walkthrough

Optimal Greedy Bit Manipulation Algorithm

1. Start with the input integer n and initialize an operation counter to 0.
2. Continue processing until n becomes 1.
3. If n is even, divide it by 2.

This is always optimal because halving reduces the number as quickly as possible. 4. If n is odd, decide whether to increment or decrement.

For odd numbers, inspect the binary representation:

• If n == 3, subtract 1
• Else if the last two bits are 11, add 1
• Otherwise subtract 1

5. Increment the operation counter after every transformation.
6. Return the total operation count once n reaches 1.

Why it works

The algorithm works because powers of two are ideal states. Once a number becomes a power of two, repeated division by 2 reduces it to 1 very quickly.

For odd numbers, adding or subtracting 1 converts the number into an even number. The greedy strategy chooses the operation that creates the largest number of trailing zero bits in binary, because that enables multiple future divisions by 2.

The only special case is 3:

3 -> 2 -> 1   (2 steps)
3 -> 4 -> 2 -> 1   (3 steps)

So 3 must use subtraction.

Python Solution

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

        while n != 1:
            if n % 2 == 0:
                n //= 2
            else:
                if n == 3 or (n & 2) == 0:
                    n -= 1
                else:
                    n += 1

            operations += 1

        return operations

The implementation follows the greedy algorithm directly.

The variable operations tracks how many transformations have been performed.

Inside the loop:

• Even numbers are halved immediately
• Odd numbers are analyzed using bit manipulation

The expression:

(n & 2) == 0

checks the second least significant bit.

For example:

5 = 101
5 & 2 = 0

This means the binary form ends in 01, so subtracting is preferable.

Meanwhile:

7 = 111
7 & 2 = 2

This means the binary form ends in 11, so adding is preferable.

The loop continues until n becomes 1.

Go Solution

func integerReplacement(n int) int {
    operations := 0

    for n != 1 {
        if n%2 == 0 {
            n /= 2
        } else {
            if n == 3 || (n&2) == 0 {
                n--
            } else {
                n++
            }
        }

        operations++
    }

    return operations
}

The Go implementation is nearly identical to the Python version.

One important consideration is integer overflow. The problem allows values up to 2^31 - 1, and adding 1 to this value could overflow a signed 32-bit integer in some languages.

Go's int type is typically 64-bit on modern platforms, so this implementation safely handles the increment operation. If using a strict 32-bit integer type, additional care would be required.

Bitwise operations in Go use the same syntax as many C-style languages, so checking (n & 2) works exactly as it does in Python.

Worked Examples

Example 1

Input: n = 8

Step	Current n	Operation	Result
1	8	divide by 2	4
2	4	divide by 2	2
3	2	divide by 2	1

Total operations: 3

Example 2

Input: n = 7

Binary representation:

7 = 111

Since the last two bits are 11, incrementing is better.

Step	Current n	Decision	Result
1	7	add 1	8
2	8	divide by 2	4
3	4	divide by 2	2
4	2	divide by 2	1

Total operations: 4

Example 3

Input: n = 4

Step	Current n	Operation	Result
1	4	divide by 2	2
2	2	divide by 2	1

Total operations: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Each operation significantly reduces the number
Space	O(1)	Only a few variables are used

The number shrinks rapidly because every even step halves the value. Even odd-number adjustments are designed to quickly create divisible-by-two states.

Since repeated halving dominates the process, the total number of iterations is proportional to the number of bits in n, which is O(log n).

The algorithm uses constant extra memory because it only stores counters and the current value.

Test Cases

solution = Solution()

assert solution.integerReplacement(1) == 0   # already at 1
assert solution.integerReplacement(2) == 1   # single division
assert solution.integerReplacement(3) == 2   # special-case handling
assert solution.integerReplacement(4) == 2   # repeated halving
assert solution.integerReplacement(7) == 4   # prefers increment
assert solution.integerReplacement(8) == 3   # pure power of two
assert solution.integerReplacement(15) == 5  # multiple greedy increments
assert solution.integerReplacement(5) == 3   # prefers decrement
assert solution.integerReplacement(6) == 3   # even then odd
assert solution.integerReplacement(1024) == 10  # large power of two
assert solution.integerReplacement(2147483647) == 32  # maximum constraint

Test Case Summary

Test	Why
n = 1	Verifies base case
n = 2	Smallest reducible even number
n = 3	Validates special-case logic
n = 4	Simple repeated division
n = 7	Tests increment strategy
n = 8	Pure power-of-two reduction
n = 15	Consecutive 11 binary endings
n = 5	Tests decrement strategy
n = 6	Mixed even and odd transitions
n = 1024	Large power of two
n = 2147483647	Maximum allowed input

Edge Cases

Edge Case 1: n = 1

This is the smallest possible input and also the termination condition.

A buggy implementation might accidentally perform unnecessary operations or enter the loop incorrectly. The provided solution handles this naturally because the loop condition:

while n != 1:

fails immediately, returning 0.

Edge Case 2: n = 3

This is the only odd number where the greedy "add when ending in 11" rule fails.

Binary:

3 = 11

Normally, numbers ending in 11 are incremented. However:

3 -> 4 -> 2 -> 1

takes three operations, while:

3 -> 2 -> 1

takes only two.

The implementation explicitly checks:

if n == 3

to guarantee the optimal path.

Edge Case 3: Maximum Integer Value

The largest input is:

2147483647 = 2^31 - 1

Adding 1 produces:

2147483648

which may overflow in languages using 32-bit signed integers.

The implementation avoids issues by using Python's arbitrary-precision integers and Go's platform-sized int, which is typically 64-bit on modern systems.

This ensures correctness even at the boundary of the constraint range.