Problem Statement in English

You are given two integers, num1 and num2.

In one operation, you can choose an integer $i$ in the range $[0, 60]$ and subtract $2^i + \text{num2}$ from num1.

Return the minimum number of operations required to make num1 equal to $0$.

If it is impossible to make num1 equal to $0$, return $-1$.

Approach

Since each operation subtracts num2 from num1, in k operations, we will have subtracted k * num2 from num1.

Therefore, in order to make num1 equal to 0, we need to find a k such that:

$num1 - k * num2 = \text{sum of } k \text{ powers of 2}$

Here’s the next hack. The question itself says that we can choose $i$ in the range $[0, 60]$. This means that the maximum number of distinct powers of $2$ we can choose is $61$ (from $2^0$ to $2^{60}$).

So we exploit this by simply iterating over possible values of $k$ from $1$ to $61$ and checking if we can express x = num1 - k * num2 as the sum of $k$ distinct powers of $2$.

In particular, we need to check if the number of set bits in $x$ is less than or equal to $k$, because that tells us if we can express it as the sum of $k$ or fewer distinct powers of $2$.

If for a given $k$, $x$ is less than $k$, it means we cannot express it as the sum of $k$ distinct powers of $2$, since it’s then definitely less than $2^k$.

Solution in Python


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

Complexity

  • Time: $O(1)$
    Since we perform 60 iterations at most.

  • Space: $O(1)$
    Since we use a constant amount of space.

Mistakes I made

I had to check the solution :(

And we are done.