Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

After k operations, the selected powers of two must sum to num1 - k*num2. A positive integer needs at least its set-bit count many powers of two, using its binary expansion, and can use at most its own value many, using only ones. Splitting a larger power into two equal powers increases the number of terms by one, so every count between those bounds is possible.

Approach

Try operation counts in increasing order, using the reference implementation's range from one through 32. For each, compute the required power sum remaining. Accept when bitCount(remaining) <= k <= remaining; the latter comparison also rejects nonpositive sums. Return the first accepted count, or -1 after the checked range. Exact-integer arithmetic is used to evaluate the intermediate sums and bit counts.

class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
        for k in range(1, 33):
            curr = num1 - k * num2
            if k >= curr.bit_count() and curr >= k:
                return k

        return -1

Complexity analysis

There are exactly 32 candidate counts. Let B bound the intermediate integer bit length. Python's fixed-small-multiplier arithmetic and bit_count use O(B) bit work per candidate. JavaScript scans the bits with repeated BigInt shifts; accounting for shrinking integer copies gives a conservative O(B^2) bit-time bound, not O(B). Both use O(B) peak auxiliary bits. Under the actual input constraints, intermediate magnitudes are below 33 * 10^9 < 2^35, so B <= 35 and both time and space are bounded constants.