2749: Minimum-Operations-to-Make-the-Integer-Zero
Medium

The question basically mentions that you are given two integers num1 and num2, and are trying to apply the minimum number of operations to make num1 equal to 0. Each operation in this case is subtracting 2^i + num2 to num1, where i is an integer between [0, 60].

In a general sense, if we apply n operations, then we will always subtract n * num2 from num1, meaning we only need to work out if it is possible to sum n powers of 2 to form num1 - n * num2.

If we can convert num1 - n * num2 into binary, then the minimum number of powers of 2 that we need is simply the number of set bits. Consequently, since 2^0 = 1 is the smallest power of 2 that can be formed, the maximum number of powers of 2 that we need is simply num1 - n * num2.

Therefore, it implies that as long as n is:

then we have a feasible solution.

Now, for the algorithm, we first define the number of operations:

int numberOfOperations = 0;

Then, we know that a solution is always feasible as long as num1 > 0, since 2^i is always positive:

while (num1 > 0) {
    // to be continued
}

so for each iteration, we want to define whether a solution is feasible for num1 - n * num2. Therefore, we start off by subtracting num2 from num1 and incrementing numberOfOperations:

num1 -= num2;
++numberOfOperations;

Next, we need to find how many bits are set in num1 - n * num2:

int setBitCounter = 0;
for (long long copy = num1; copy > 0; copy >>= 1) {
    if (copy % 2 == 1) {
        ++setBitCounter;
    }
}

Finally, we check if num1 - n * num2 < numberOfOperations. If it is true, then we early return -1 since:

$$\begin{align*} &\text{num}_2 - n \times \text{num}_2 < \text{numberOfOperations} \\ &\iff \text{num}_1 - n \times \text{num}_2 < \text{numberOfOperations} \times 1 \\ &\implies \text{num}_1 - n \times \text{num}_2 < \text{numberOfOperations} \times 2^i \\ \end{align*}$$

Else, we can check if setBitCounter <= numberOfOperations since the conditional statement will hold true if and only if a valid solution exists.

if (num1 < numberOfOperations) {
    return -1;
}
if (setBitCounter <= numberOfOperations) {
    return numberOfOperations;
}

code

class Solution {
public:
    int makeTheIntegerZero(long long num1, long long num2) {
        int numberOfOperations = 0;
        
        while (num1 > 0) {
            num1 -= num2;
            ++numberOfOperations;

            int setBitCounter = 0;
            for (long long copy = num1; copy > 0; copy >>= 1) {
                if (copy % 2 == 1) {
                    ++setBitCounter;
                }
            }

            if (num1 < numberOfOperations) {
                return -1;
            }
            if (setBitCounter <= numberOfOperations) {
                return numberOfOperations;
            }
        }
        return -1;
    }
};

complexity

time taken