Integer Replacement
Medium · Greedy · Explanation and code example
Greedy Bit Reduction
How it works
Even values reduce directly by shifting right. For an odd value, choose the increment or decrement that creates more trailing zero bits, enabling more divisions by two. Three is the exception: decrementing to two reaches one faster than incrementing to four.
Steps
- Divide even values by two.
- For odd values, decrement three or a value ending in binary 01; otherwise increment.
- Count operations until one.
Complexity
- Time: O(log n).
- Space: O(1).
Things to watch for
- Treat three specially.
- Use a widened integer in C++ so incrementing INT_MAX does not overflow.
- For n = 1, the answer is zero.
Python code example
class Solution:
def integerReplacement(self, n: int) -> int:
ans = 0
while n > 1:
if n % 2 == 0: # `n` ends in 0.
n >>= 1
elif n == 3 or (n >> 1 & 1) == 0: # `n` = 3 or ends in 0b01.
n -= 1
else: # `n` ends in 0b11.
n += 1
ans += 1
return ans
C++ code example
class Solution {
public:
int integerReplacement(long n) {
int ans = 0;
for (; n > 1; ++ans)
if (n % 2 == 0) // `n` ends in 0.
n >>= 1;
else if (n == 3 || (n >> 1 & 1) == 0) // `n` = 3 or ends in 0b01.
--n;
else // `n` ends in 0b11.
++n;
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.