Minimum Operations to Make the Integer Zero

1
Input: num1 = 3, num2 = -2
2
Output: 3
3
Explanation: We can make 3 equal to 0 with the following operations:
4

5
- We choose i = 2 and subtract 2^2 + (-2) from 3, 3 - (4 + (-2)) = 1.
6
- We choose i = 2 and subtract 2^2 + (-2) from 1, 1 - (4 + (-2)) = -1.
7
- We choose i = 0 and subtract 2^0 + (-2) from -1, (-1) - (1 + (-2)) = 0.
8

9
It can be proven, that 3 is the minimum number of operations that we need to perform.

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

1
class Solution {
2
public:
3
    int makeTheIntegerZero(int num1, int num2) {
4
        // check if (num1 -  k * num2) is possible w/ k terms of (power of 2)
5
        int k = 1;
6
        while (true) {
7
            // subtract num2 for k times (step k)
8
            long long num = num1 - (long long)num2 * k;
9

10
            // if we choose i for only 0, at least k is needed (1+1+1+1.... = k)
11
            if (num < k) return -1;
12

13
            // when num of set bits is <= k, we can make num w/ k terms of (power of 2)
14
            else if (bitCnt(num) <= k) return k;
15

16
            // check for next step
17
            ++k;
18
        }
19
    }
20

21
    // Brian Kernighan’s Algorithm
22
    int bitCnt(long long num) {
23
        int cnt = 0;
24
        while (num != 0) {
25
            ++cnt;
26
            num &= (num-1);
27
        }
28
        return cnt;
29
    }
30

31
    // or use __builtin_popcountll(num)
32
    int bitCnt2(long long num) {
33
        return __builtin_popcountll(num);
34
    }
35
};

// convert this:
num1_final = num1 - k * num2 - (2^i_1 + 2^i_2 + ... + 2^i_k)

// to this:
num1 - k * num2 = 2^i_1 + 2^i_2 + ... + 2^i_k