You are given a positive integer n, you can do the following operation any number of times:
- Add or subtract a power of
2 from n.
Return the minimum number of operations to make n equal to 0.
A number x is power of 2 if x == 2i where i >= 0.
Example 1:
Input: n = 39
Output: 3
Explanation: We can do the following operations:
- Add 20 = 1 to n, so now n = 40.
- Subtract 23 = 8 from n, so now n = 32.
- Subtract 25 = 32 from n, so now n = 0.
It can be shown that 3 is the minimum number of operations we need to make n equal to 0.
Example 2:
Input: n = 54
Output: 3
Explanation: We can do the following operations:
- Add 21 = 2 to n, so now n = 56.
- Add 23 = 8 to n, so now n = 64.
- Subtract 26 = 64 from n, so now n = 0.
So the minimum number of operations is 3.
Constraints:
## Solution(Python)
```Python
class Solution:
def minOperations(self, n: int) -> int:
return self.minOptimnalOperations(n)
def minOptimnalOperations(self, n: int) -> int:
# Initialize result counter and consecutive 1-bits counter
operations = 0
consecutive_ones = 0
# Process each bit of n from right to left
while n > 0:
# Check if the current least significant bit is 1
if n & 1:
# Increment counter for consecutive 1-bits
consecutive_ones += 1
elif consecutive_ones > 0:
# We hit a 0 after seeing 1s, process the group of 1s
operations += 1
# Reset counter: if we had exactly one 1, start fresh
# Otherwise, carry over 1 (for cases like 11 -> 100)
consecutive_ones = 0 if consecutive_ones == 1 else 1
# Right shift to check the next bit
n >>= 1
# Handle any remaining consecutive 1-bits after the loop
if consecutive_ones == 1:
# Single 1-bit requires one operation
operations += 1
elif consecutive_ones > 1:
# Multiple consecutive 1-bits require two operations
operations += 2
return operations
def mindpOperations(self, n: int) -> int:
@lru_cache(maxsize=None)
def dp(x):
if x == 0:
return 0
if x == 1:
return 1
if x % 2 == 0:
return dp(x // 2)
else:
return 1 + min(dp(x // 2), dp((x + 1) // 2))
return dp(n)
```