README.md

2749. Minimum Operations to Make the Integer Zero (Medium)

You are given two integers num1 and num2.

In one operation, you can choose integer i in the range [0, 60] and subtract 2i + num2 from num1.

Return the integer denoting the minimum number of operations needed to make num1 equal to 0.

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

 

Example 1:

Input: num1 = 3, num2 = -2
Output: 3
Explanation: We can make 3 equal to 0 with the following operations:
- We choose i = 2 and substract 22 + (-2) from 3, 3 - (4 + (-2)) = 1.
- We choose i = 2 and substract 22 + (-2) from 1, 1 - (4 + (-2)) = -1.
- We choose i = 0 and substract 20 + (-2) from -1, (-1) - (1 + (-2)) = 0.
It can be proven, that 3 is the minimum number of operations that we need to perform.

Example 2:

Input: num1 = 5, num2 = 7
Output: -1
Explanation: It can be proven, that it is impossible to make 5 equal to 0 with the given operation.

 

Constraints:

• 1 <= num1 <= 109
• -109 <= num2 <= 109

Related Topics:
Bit Manipulation, Brainteaser

Similar Questions:

• Broken Calculator (Medium)
• Minimum Operations to Reduce X to Zero (Medium)

Solution 1.

Assume we made K operations with $i_1, i_2, ..., i_k$, then we have

$$a-(2^{i_1}+2^{i_2}+\cdots+2^{i_k}) - K * b = 0$$

$$a-K*b = 2^{i_1}+2^{i_2}+\cdots+2^{i_k}$$

Let x = a - K * b. We try K = 1, 2, 3, ....

If x becomes negative, we should return -1.

Otherwise, we need to check if x can be expressed with K powers of 2.

Say x = 101 in binary. We can express x with number of bits in x = 2 operations at minimum, and with x = 5 operations at maximum.

So, as long as K is within [{number of bits in x}, x], we can return this K.

// OJ: https://leetcode.com/problems/minimum-operations-to-make-the-integer-zero
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
    int makeTheIntegerZero(int a, int b) {
        for (long long k = 1; true; ++k) {
            long long x = a - k * b;
            if (x <= 0) break;
            if (k >= __builtin_popcountll(x) && k <= x) return k;
        }
        return -1;
    }
};