Integer Replacement solution and explanation
Google
9 more videos on this problem
LeetCode 397. Integer ReplacementHappy Coding · 13:15 · 3K views
Leetcode 397 Integer ReplacementMath Geeks · 6:31 · 1K views
Cracking SDE interview. Integer Replacement. Leetcode #397 (medium) task.Evergreen's coderzone · 25:00 · 1K views
Integer ReplacementScott · 2:40 · 500 views
397. Integer Replacement Leetcode by RecursionNinja Yogiz · 2:23 · 445 views
LeetCode 397 | Integer Replacement | JavaSleepy Cracker · 5:42 · 328 views
Integer Replacement (JS) LeetcodeMB Tutorials · 3:40 · 199 views
LeetCode 397: Integer Replacement | Greedy + Bit Manipulation Explained 🔥 | C++ Optimal SolutionPriyabrata Sahoo · 6:36 · 74 views
Leetcode 397. Integer Replacement (bfs)LetsCode · 7:46 · 59 views
No Sound Leetcode 397: Integer ReplacementExtremeProgrammer · 0:56 · 35 views
The problem
Given a positive integer n, you can apply one of the following operations:
- If
nis even, replacenwithn / 2. - If
nis odd, replacenwith eithern + 1orn - 1.
Return the minimum number of operations needed for n to become 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 <= 231 - 1
Approach overview
Problem Overview: Given a positive integer n, reduce it to 1 using the minimum number of operations. If n is even you can divide by 2, and if it is odd you can either increment or decrement by 1. The challenge is choosing the correct direction for odd numbers to minimize the total number of steps.
Approach 1: Recursive Approach with Memoization (Time: O(log n), Space: O(log n))
This approach models the problem as a recursive decision tree. For every odd number n, you evaluate both possibilities: n + 1 and n - 1. For even numbers, the decision is deterministic because dividing by two is always optimal. Memoization stores previously computed results in a hash map so repeated states are not recomputed. Since the value roughly halves whenever it becomes even, the recursion depth grows proportional to log n. This method is straightforward to reason about and demonstrates classic dynamic programming with memoization, but it still explores both branches for odd values before caching results.
Approach 2: Greedy with Bit Manipulation (Time: O(log n), Space: O(1))
The optimal approach relies on binary patterns. When n is even, right shifting (n / 2) removes a trailing zero bit, which always reduces the number efficiently. When n is odd, the decision between n + 1 and n - 1 depends on the last two bits. If n % 4 == 1, decrementing produces more trailing zeros and speeds up future divisions. If n % 4 == 3, incrementing is better because it often collapses a sequence of ones in binary. The only exception is n == 3, where decrementing reaches the optimal path faster. This strategy uses simple bit checks and avoids recursion entirely, making it a clean example of combining greedy algorithms with bit manipulation.
Recommended for interviews: Interviewers usually expect the greedy bit manipulation insight because it reduces the search space and achieves O(log n) time with constant space. Starting with the recursive memoized solution shows correct problem modeling and understanding of dynamic programming. Moving to the greedy bit-based rule demonstrates deeper optimization and familiarity with binary reasoning.
Approach 1: Greedy Approach with Bit Manipulation
The greedy approach involves observing the binary representation of numbers and making decisions on whether to increment or decrement based on the number of trailing zeros. If even, always divide by 2. If odd, decide between incrementing or decrementing based on the result that gives fewer operations.
class Solution:
def integerReplacement(self, n: int) -> int:
count = 0
while n != 1:
if n % 2 == 0:
n //= 2
else:
if n == 3 or (n & 2) == 0:
n -= 1
else:
n += 1
count += 1
return count
# Example usage:
sol = Solution()
print(sol.integerReplacement(8)) # Output: 3
print(sol.integerReplacement(7)) # Output: 4
print(sol.integerReplacement(4)) # Output: 2public class Solution {
public int integerReplacement(int n) {
int count = 0;
while (n != 1) {
if ((n & 1) == 0) {
n >>>= 1;
} else {
if (n == 3 || (n & 2) == 0) {
n--;
} else {
n++;
}
}
count++;
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.integerReplacement(8)); // Output: 3
System.out.println(sol.integerReplacement(7)); // Output: 4
System.out.println(sol.integerReplacement(4)); // Output: 2
}
}#include <iostream>
class Solution {
public:
int integerReplacement(int n) {
int count = 0;
while (n != 1) {
if (n % 2 == 0) {
n /= 2;
} else {
if (n == 3 || (n & 2) == 0) {
--n;
} else {
++n;
}
}
++count;
}
return count;
}
};
int main() {
Solution sol;
std::cout << sol.integerReplacement(8) << std::endl; // Output: 3
std::cout << sol.integerReplacement(7) << std::endl; // Output: 4
std::cout << sol.integerReplacement(4) << std::endl; // Output: 2
return 0;
}function integerReplacement(n) {
let count = 0;
while (n !== 1) {
if (n % 2 === 0) {
n /= 2;
} else {
if (n === 3 || (n & 2) === 0) {
n--;
} else {
n++;
}
}
count++;
}
return count;
}
console.log(integerReplacement(8)); // Output: 3
console.log(integerReplacement(7)); // Output: 4
console.log(integerReplacement(4)); // Output: 2;#include <stdio.h>
int integerReplacement(int n) {
int count = 0;
while (n != 1) {
if (n % 2 == 0) {
n /= 2;
} else {
if (n == 3 || (n & 2) == 0) {
--n;
} else {
++n;
}
}
++count;
}
return count;
}
int main() {
printf("%d\n", integerReplacement(8)); // Output: 3
printf("%d\n", integerReplacement(7)); // Output: 4
printf("%d\n", integerReplacement(4)); // Output: 2
return 0;
}using System;
public class Solution {
public int IntegerReplacement(int n) {
int count = 0;
while (n != 1) {
if ((n & 1) == 0) {
n >>= 1;
} else {
if (n == 3 || (n & 2) == 0) {
n--;
} else {
n++;
}
}
count++;
}
return count;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.IntegerReplacement(8)); // Output: 3
Console.WriteLine(sol.IntegerReplacement(7)); // Output: 4
Console.WriteLine(sol.IntegerReplacement(4)); // Output: 2
}
}The Python implementation effectively blends arithmetic and bitwise operations to decide the operation reducing n. The integer division //= 2 neatly divides integers when even, contributing to clarity and simplicity of code. For odd n, the bit manipulation based decision retains performance efficiency.
Time Complexity: O(log n), leveraging division and addition/subtraction strategically.
Space Complexity: O(1), requiring minimal extra space beyond the integer size.
Approach 2: Recursive Approach with Memoization
The recursive approach leverages memoization to store previously computed results, avoiding redundant calculations. The transition involves conditional checks for even and odd numbers and memoizes solutions to subproblems, efficiently calculating the minimal operations.
class Solution:
def __init__(self):
self.memo = {}
def integerReplacement(self, n: int) -> int:
if n == 1:
return 0
if n in self.memo:
return self.memo[n]
if n % 2 == 0:
self.memo[n] = 1 + self.integerReplacement(n // 2)
else:
self.memo[n] = 1 + min(self.integerReplacement(n - 1), self.integerReplacement(n + 1) if n != 2147483647 else self.integerReplacement(n - 1))
return self.memo[n]
# Example usage:
sol = Solution()
print(sol.integerReplacement(8)) # Output: 3
print(sol.integerReplacement(7)) # Output: 4
print(sol.integerReplacement(4)) # Output: 2import java.util.HashMap;
public class Solution {
private HashMap<Integer, Integer> memo = new HashMap<>();
public int integerReplacement(int n) {
if (n == 1) return 0;
if (memo.containsKey(n)) return memo.get(n);
if (n % 2 == 0) {
memo.put(n, 1 + integerReplacement(n / 2));
} else {
memo.put(n, 1 + Math.min(integerReplacement(n - 1), integerReplacement((n == Integer.MAX_VALUE) ? n - 1 : n + 1)));
}
return memo.get(n);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.integerReplacement(8)); // Output: 3
System.out.println(sol.integerReplacement(7)); // Output: 4
System.out.println(sol.integerReplacement(4)); // Output: 2
}
}#include <iostream>
#include <unordered_map>
class Solution {
public:
int integerReplacement(int n) {
if (n == 1) return 0;
if (memo.find(n) != memo.end()) return memo[n];
if (n % 2 == 0) {
return memo[n] = 1 + integerReplacement(n / 2);
} else {
return memo[n] = 1 + std::min(integerReplacement(n - 1), integerReplacement(n == INT_MAX ? n - 1 : n + 1));
}
}
private:
std::unordered_map<int, int> memo;
};
int main() {
Solution sol;
std::cout << sol.integerReplacement(8) << std::endl; // Output: 3
std::cout << sol.integerReplacement(7) << std::endl; // Output: 4
std::cout << sol.integerReplacement(4) << std::endl; // Output: 2
return 0;
}function integerReplacement(n) {
const memo = {};
const helper = (x) => {
if (x === 1) return 0;
if (memo[x]) return memo[x];
if (x % 2 === 0) {
return memo[x] = 1 + helper(x / 2);
} else {
return memo[x] = 1 + Math.min(helper(x - 1), helper(x + 1));
}
};
return helper(n);
}
console.log(integerReplacement(8)); // Output: 3
console.log(integerReplacement(7)); // Output: 4
console.log(integerReplacement(4)); // Output: 2;#include <stdio.h>
#include <limits.h>
#include <string.h>
int helper(int n, int *dp) {
if (n == 1) return 0;
if (dp[n] != -1) return dp[n];
if (n % 2 == 0) {
dp[n] = 1 + helper(n / 2, dp);
} else {
dp[n] = 1 + (n == INT_MAX ? helper(n - 1, dp) : fmin(helper(n - 1, dp), helper(n + 1, dp)));
}
return dp[n];
}
int integerReplacement(int n) {
int dp[n+1];
memset(dp, -1, sizeof(dp));
return helper(n, dp);
}
int main() {
printf("%d\n", integerReplacement(8)); // Output: 3
printf("%d\n", integerReplacement(7)); // Output: 4
printf("%d\n", integerReplacement(4)); // Output: 2
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
private Dictionary<int, int> memo = new Dictionary<int, int>();
public int IntegerReplacement(int n) {
if (n == 1) return 0;
if (memo.TryGetValue(n, out int res)) return res;
if (n % 2 == 0) {
res = 1 + IntegerReplacement(n / 2);
} else {
res = 1 + Math.Min(IntegerReplacement(n - 1), IntegerReplacement(n == int.MaxValue ? n - 1 : n + 1));
}
memo[n] = res;
return res;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.IntegerReplacement(8)); // Output: 3
Console.WriteLine(sol.IntegerReplacement(7)); // Output: 4
Console.WriteLine(sol.IntegerReplacement(4)); // Output: 2
}
}The Python solution leverages a dictionary to memorize subproblem results, recursively optimizing the steps to 1. The `integerReplacement` function evaluates both decrement and increment paths for odd cases, storing outcomes to enhance execution efficiency by avoiding redundant calculations.
Time Complexity: O(log n), through efficient recursion and memoization technique.
Space Complexity: O(log n), with storage use confined by recursion depth and memo entries.
Approach 3: Default Approach
func integerReplacement(n int) int {
ans := 0
for n != 1 {
if (n & 1) == 0 {
n >>= 1
} else if n != 3 && (n&3) == 3 {
n++
} else {
n--
}
ans++
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Bit Manipulation | Time Complexity: O(log n), leveraging division and addition/subtraction strategically. |
| Recursive Approach with Memoization | Time Complexity: O(log n), through efficient recursion and memoization technique. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(log n) | O(log n) | Good for understanding the decision tree and demonstrating dynamic programming techniques. |
| Greedy with Bit Manipulation | O(log n) | O(1) | Preferred optimal solution for interviews and production due to constant space and simple bit checks. |
Frequently asked questions
Is Integer Replacement easy or hard?
Integer Replacement is generally classified as a medium difficulty problem. The base operations are simple, but choosing the optimal action for odd numbers requires recognizing binary patterns. Many candidates initially attempt recursion before discovering the greedy bit manipulation optimization.
Integer Replacement Python/Java solution
Both Python and Java implementations typically follow the greedy rule using bit checks. Even numbers are divided by two, while odd numbers decide between increment and decrement based on n % 4 and the special case n == 3. The logic is identical across languages and runs in O(log n) time.
How to solve Integer Replacement in O(log n)?
Use a greedy rule based on the binary representation of n. If n is even, divide it by 2. If n is odd, check the last two bits: decrement when n % 4 == 1 and increment when n % 4 == 3, except for n == 3 where decrementing is optimal. This ensures the number gains more trailing zeros, enabling faster halving steps.
What is the best approach for Integer Replacement?
The greedy approach with bit manipulation is considered the best solution. It observes patterns in the binary representation of the number and chooses n+1 or n-1 based on the last two bits. This reduces the number of steps needed before repeated divisions by two. The algorithm runs in O(log n) time and uses O(1) space.
Is Integer Replacement asked at Google/Amazon/Meta?
Integer Replacement appears in interviews at large tech companies because it tests reasoning about recursion, dynamic programming, and binary representation. Variations of the problem have been reported in interviews at companies like Google and Amazon where candidates must identify the greedy bit pattern optimization.
What data structure is used in Integer Replacement?
The memoized recursive approach uses a hash map or dictionary to store previously computed results. This prevents recomputation of states when exploring n+1 and n-1 paths. The greedy solution does not require additional data structures and relies only on integer operations and bit checks.
What is the time complexity of Integer Replacement?
The optimal solutions run in O(log n) time because each operation either halves the number or converts it into a form that quickly becomes divisible by two. Since the value shrinks exponentially through division, the total number of operations grows proportional to the number of bits in n.