MediumNo. 0397
Integer Replacement — LeetCode 397 Python Solution
- Pattern
- Bit Manipulation
- Topics
- Greedy, Bit Manipulation, Memoization, Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given a positive integer n, you can apply one of the following operations: If n is even, replace n with n / 2. If n is odd, replace n with either n + 1 or n - 1.
Example
- Input
- n = 8
- Output
- 3
- Explanation
- 8 -> 4 -> 2 -> 1
Python solution
class Solution:
def integerReplacement(self, n: int) -> int:
ans = 0
while n != 1:
if (n & 1) == 0:
n >>= 1
elif n != 3 and (n & 3) == 3:
n += 1
else:
n -= 1
ans += 1
return ansComplexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 397. Integer Replacement is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0464 | Can I Win | Medium |
| 0638 | Shopping Offers | Medium |
| 0698 | Partition to K Equal Sum Subsets | Medium |
| 1611 | Minimum One Bit Operations to Make Integers Zero | Hard |
| 1659 | Maximize Grid Happiness | Hard |
| 1815 | Maximum Number of Groups Getting Fresh Donuts | Hard |
Frequently asked questions
- How hard is LeetCode 397. Integer Replacement?
LeetCode 397. Integer Replacement is rated Medium on LeetCode.
- What topics does LeetCode 397. Integer Replacement cover?
LeetCode 397. Integer Replacement is tagged Greedy, Bit Manipulation, Memoization and Dynamic Programming on LeetCode.