Integer Replacement

Medium
707.

Integer Replacement

Integer Replacement is a medium coding problem on dynamic programming, greedy and bit manipulation, asked in Amazon, Google and Meta interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var integerReplacement = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Integer Replacement — Solution in Python, Java & C++

Integer Replacement solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Integer Replacement is a medium coding problem on dynamic programming, greedy and bit manipulation, asked in Amazon, Google and Meta interviews.

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

Hints for Integer Replacement

  1. Hint 1

    Even numbers have no choice — halve them.

  2. Hint 2

    For an odd n, the choice is n - 1 or n + 1; whichever has more trailing zeros wins, because those are free halvings.

  3. Hint 3

    That reduces to a two-bit test: n % 4 == 1 means subtract, n % 4 == 3 means add — except for n = 3, where subtracting is better.

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

  1. While n > 1: if n is even, halve it.
  2. If n is odd and n == 3 or n % 4 == 1, subtract 1.
  3. Otherwise add 1.
  4. 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

Java

public static int integerReplacement(int n) {
    long v = n;
    int steps = 0;
    while (v > 1) {
        if (v % 2 == 0) v /= 2;
        else if (v == 3 || v % 4 == 1) v -= 1;
        else v += 1;
        steps++;
    }
    return steps;
}

C++

int integerReplacement(int n) {
    long long v = n;
    int steps = 0;
    while (v > 1) {
        if (v % 2 == 0) v /= 2;
        else if (v == 3 || v % 4 == 1) v -= 1;
        else v += 1;
        steps++;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Greedy Algorithms