Minimum Operations to Make the Integer Zero

main.md

Question

Approach

The key idea is to model each operation as subtracting $2^i + \text{num2}$ from num1. After $k$ operations, this means we subtract $k \cdot \text{num2} + S$, where $S$ is the sum of $k$ powers of two (with repetition allowed). Rearranging gives $S = \text{num1} - k \cdot \text{num2}$. For a given $k$, this $S$ must be non-negative and representable as a sum of exactly $k$ powers of two. The smallest number of powers of two needed for $S$ is its binary popcount, and the maximum number is $S$ itself (all ones). So the condition is $\text{popcount}(S) \leq k \leq S$. I loop over $k$ from 1 up to 60 (enough since $2^{60}$ is larger than the constraints), compute $S$, and return the first valid $k$. If no such $k$ works, the answer is $-1$.

Implementation

class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
        for k in range(1, 61):
            s = num1 - k * num2
            if s < 0:
                continue
            if s.bit_count() <= k <= s:
                return k
        return -1

Complexities

• Time: O(1)
• Space: O(1)