Integer Replacement — Medium Problem & Solution

Starting from n, each step must either halve the value (only when it is even) or add or subtract 1 (only when it is odd).

Difficulty: Medium
Topics: Dynamic Programming, Greedy, Bit Manipulation
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Starting from n, each step must either halve the value (only when it is even) or add or subtract 1 (only when it is odd).

Return the minimum number of steps needed to reach 1.

Example 1

Input: n = 8
Output: 3
Explanation: 8 → 4 → 2 → 1.

Example 2

Input: n = 7
Output: 4
Explanation: 7 → 8 → 4 → 2 → 1 (or 7 → 6 → 3 → 2 → 1).

Example 3

Input: n = 4
Output: 2

Constraints

1 <= n <= 1000000000

How to solve Integer Replacement

Halving is forced on even values. On an odd value, picking the neighbour with more trailing zeros buys more free halvings, and the two lowest bits decide which neighbour that is.

Approach

While n > 1: if n is even, halve it.
If n is odd and n == 3 or n % 4 == 1, subtract 1.
Otherwise add 1.
Count every step.

Why it works

For odd n, exactly one of n - 1 and n + 1 is divisible by 4. Moving to that one gains at least two halvings for the price of one step, which dominates the alternative — except at n = 3, where n + 1 = 4 and n - 1 = 2 both reach 1 in two more steps and subtracting is never worse.

Complexity

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

Pitfalls

At the 32-bit ceiling n + 1 overflows — carry the value in a 64-bit variable.
Always subtracting on an odd value is wrong for n = 7 and many larger values.
Without the special case for 3, the greedy goes 3 → 4 → 2 → 1, which is the same length here but sets up worse choices in a memoised formulation.

Reference solution

Python

def integerReplacement(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

JavaScript

var integerReplacement = function(n) {
    var v = n, steps = 0;
    while (v > 1) {
        if (v % 2 === 0) v = v / 2;
        else if (v === 3 || v % 4 === 1) v -= 1;
        else v += 1;
        steps++;
    }
    return steps;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 195 dynamic programming problems · the whole catalogue