2571-minimum-operations-to-reduce-an-integer-to-0

Try it on leetcode

Description

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:

• 1 <= n <= 105

Solution(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)