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.
- 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
Hints for Integer Replacement
Hint 1
Even numbers have no choice — halve them.
Hint 2
For an odd
n, the choice isn - 1orn + 1; whichever has more trailing zeros wins, because those are free halvings.Hint 3
That reduces to a two-bit test:
n % 4 == 1means subtract,n % 4 == 3means add — except forn = 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
- While
n > 1: ifnis even, halve it. - If
nis odd andn == 3orn % 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 + 1overflows — carry the value in a 64-bit variable. - Always subtracting on an odd value is wrong for
n = 7and many larger values. - Without the special case for
3, the greedy goes3 → 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 stepsJava
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