Problem Description

You are given a positive integer n. You can perform the following operation any number of times:

• Add or subtract a power of 2 from n

Your goal is to return the minimum number of operations needed to make n equal to 0.

A number x is a power of 2 if x = 2^i where i >= 0 (for example: 1, 2, 4, 8, 16, ...).

The key insight is that when we look at the binary representation of n, we need to eliminate all the 1-bits. The solution uses a greedy approach by processing the binary representation from right to left:

• When encountering isolated 1-bits (like ...010...), we can eliminate them with a single subtraction operation
• When encountering consecutive 1-bits (like ...0111...), it's more efficient to add a power of 2 to convert them to ...1000..., which leaves us with just one 1-bit to handle later

The algorithm tracks consecutive 1-bits using a counter cnt:

• If the current bit is 1, increment the counter
• If the current bit is 0 and we have accumulated 1-bits:
  • If cnt == 1: one operation eliminates the single 1-bit
  • If cnt > 1: one operation (addition) converts multiple consecutive 1-bits into a single 1-bit at a higher position

After processing all bits, any remaining consecutive 1-bits are handled:

• If cnt == 1: one more operation needed
• If cnt > 1: two more operations needed (one to convert to a higher bit, one to eliminate it)

Intuition

To understand why this approach works, let's think about what happens when we add or subtract powers of 2 in binary representation.

When we subtract a power of 2 from n, we're essentially flipping a single 1-bit to 0. For example, if n = 5 (101 in binary) and we subtract 4 (100), we get 1 (001). This is straightforward for isolated 1-bits.

However, the challenge comes with consecutive 1-bits. Consider n = 7 (111 in binary). We could subtract powers of 2 three times: 7 - 4 = 3, then 3 - 2 = 1, then 1 - 1 = 0. That's 3 operations.

But here's the key insight: instead of subtracting, we can add! If we add 1 to 7, we get 8 (1000 in binary). Notice how adding 1 to 111 creates 1000 - all those consecutive 1-bits "collapse" into a single 1-bit at a higher position due to the carry propagation. Now we only need one more operation to subtract 8, giving us a total of 2 operations instead of 3.

This pattern generalizes: whenever we see consecutive 1-bits in the binary representation, it's more efficient to add a power of 2 to create a carry that eliminates all but one of them, rather than subtracting each one individually.

The algorithm essentially simulates this process by scanning through the binary representation:

• Single 1-bits can be directly eliminated (1 operation)
• Multiple consecutive 1-bits should be "collapsed" into a single higher bit through addition (1 operation), which then needs to be eliminated later (another operation)

This greedy strategy of always choosing to add when facing consecutive 1-bits and subtract for isolated 1-bits gives us the minimum number of operations.

Learn more about Greedy and Dynamic Programming patterns.

Solution Approach

The solution implements a greedy algorithm that processes the binary representation of n bit by bit from right to left using bitwise operations.

Algorithm Steps:

1. Initialize variables:

   • ans: counts the total number of operations needed
   • cnt: tracks the current number of consecutive 1-bits encountered

2. Process each bit from right to left:

   while n:
       if n & 1:  # Current bit is 1
           cnt += 1
       elif cnt:  # Current bit is 0 and we have accumulated 1-bits
           ans += 1
           cnt = 0 if cnt == 1 else 1
       n >>= 1  # Shift right to process next bit

   • When we encounter a 1-bit (n & 1 is true), we increment cnt to count consecutive 1s
   • When we encounter a 0-bit after some 1-bits:
     • If cnt == 1: We had a single isolated 1-bit, which takes 1 operation to eliminate. Reset cnt to 0
     • If cnt > 1: We had consecutive 1-bits. One operation (addition) converts them to a single 1-bit at a higher position. Set cnt = 1 to account for this carried bit

3. Handle remaining bits after the loop:

   if cnt == 1:
       ans += 1
   elif cnt > 1:
       ans += 2

   • If cnt == 1: One more operation to eliminate the final 1-bit
   • If cnt > 1: Two operations needed - one to convert consecutive 1s to a higher bit, another to eliminate that bit

Example Walkthrough:

For n = 39 (binary: 100111):

• Process bits right to left: 1, 1, 1, 0, 0, 1
• First three 1s: cnt becomes 3
• First 0: Since cnt = 3 > 1, we add 1 operation and set cnt = 1 (carried bit)
• Second 0: Since cnt = 1, we add 1 operation and set cnt = 0
• Final 1: cnt becomes 1
• After loop: cnt = 1, so add 1 more operation
• Total: 3 operations

The algorithm efficiently handles the pattern where consecutive 1-bits should be "collapsed" through addition rather than eliminated one by one through subtraction.

Example Walkthrough

Let's trace through n = 14 (binary: 1110) to illustrate the solution approach:

Initial state: n = 14 (binary: 1110), ans = 0, cnt = 0

Step 1: Process rightmost bit (0)

• n & 1 = 0, so current bit is 0
• cnt = 0, so we skip the elif block
• Shift right: n = 7 (binary: 111)

Step 2: Process next bit (1)

• n & 1 = 1, so current bit is 1
• Increment cnt = 1
• Shift right: n = 3 (binary: 11)

Step 3: Process next bit (1)

• n & 1 = 1, so current bit is 1
• Increment cnt = 2
• Shift right: n = 1 (binary: 1)

Step 4: Process next bit (1)

• n & 1 = 1, so current bit is 1
• Increment cnt = 3
• Shift right: n = 0

Step 5: Loop ends (n = 0)

• We have cnt = 3 (three consecutive 1-bits)
• Since cnt > 1, we need 2 operations:
  • First operation: Add 2 to convert 1110 to 10000 (collapsing the three 1s into a single 1)
  • Second operation: Subtract 16 to reach 0
• ans += 2

Final answer: 2 operations

This demonstrates how consecutive 1-bits (111 in positions 1-3) are more efficiently handled by adding a power of 2 to create a carry, rather than subtracting each bit individually (which would take 3 operations).

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the given integer. This is because the while loop iterates through each bit of the binary representation of n. In each iteration, we perform a right shift operation (n >>= 1), which effectively divides n by 2. The number of iterations required to reduce n to 0 through repeated division by 2 is log₂(n), hence the logarithmic time complexity.

The space complexity is O(1) as the algorithm only uses a constant amount of extra space. The variables ans and cnt are the only additional storage used, and their space requirements do not depend on the size of the input n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Remaining Bits After the Loop

The Pitfall: A common mistake is only processing bits while iterating through n and forgetting that there might be consecutive 1-bits remaining after the loop ends. This happens when the most significant bits are 1s.

Incorrect Implementation:

def minOperations(self, n: int) -> int:
    operations = 0
    consecutive_ones = 0
  
    while n > 0:
        if n & 1:
            consecutive_ones += 1
        elif consecutive_ones > 0:
            operations += 1
            consecutive_ones = 0 if consecutive_ones == 1 else 1
        n >>= 1
  
    # Missing: handling of remaining consecutive_ones!
    return operations

Why It Fails: For n = 4 (binary: 100), the loop processes the bit and consecutive_ones becomes 1, but we never add the operation needed to eliminate this final 1-bit. The function would return 0 instead of 1.

The Fix: Always check and handle any remaining consecutive 1-bits after the main loop:

if consecutive_ones == 1:
    operations += 1
elif consecutive_ones > 1:
    operations += 2

2. Incorrect Carry-Over Logic for Consecutive 1-bits

The Pitfall: When encountering a 0-bit after multiple consecutive 1-bits, incorrectly resetting consecutive_ones to 0 instead of 1. The key insight is that adding a power of 2 to consecutive 1-bits creates a carry that propagates to the next higher bit position.

Incorrect Implementation:

elif consecutive_ones > 0:
    operations += 1
    consecutive_ones = 0  # Wrong! Should be 1 when consecutive_ones > 1

Why It Fails: For n = 3 (binary: 11), after processing the two 1-bits and encountering the implicit 0 at the end, we should recognize that adding 1 converts 11 to 100, leaving us with one more 1-bit to handle. If we reset to 0, we miss accounting for this carried bit.

The Fix: Use conditional logic to properly handle the carry:

consecutive_ones = 0 if consecutive_ones == 1 else 1

3. Misunderstanding When to Increment Operations

The Pitfall: Incrementing the operation counter immediately when seeing 1-bits, rather than waiting to process a complete group of consecutive 1s.

Incorrect Implementation:

while n > 0:
    if n & 1:
        consecutive_ones += 1
        operations += 1  # Wrong! Don't count operations here
    # ...

Why It Fails: This approach counts each 1-bit as an operation, missing the optimization that consecutive 1-bits can be handled more efficiently through addition rather than multiple subtractions.

The Fix: Only increment operations when you've identified a complete group of consecutive 1-bits (when transitioning from 1s to 0, or at the end of processing):

if n & 1:
    consecutive_ones += 1  # Just count, don't add operations yet
elif consecutive_ones > 0:
    operations += 1  # Now we know the group size, add operation