Skip to content

2749. Minimum Operations to Make the Integer Zero

Description

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 subtract 22 + (-2) from 3, 3 - (4 + (-2)) = 1.
- We choose i = 2 and subtract 22 + (-2) from 1, 1 - (4 + (-2)) = -1.
- We choose i = 0 and subtract 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

Solutions

Solution 1: Enumeration

If we operate \(k\) times, then the problem essentially becomes: determining whether \(\textit{num1} - k \times \textit{num2}\) can be split into the sum of \(k\) \(2^i\)s.

Let's assume \(x = \textit{num1} - k \times \textit{num2}\). Next, we discuss in categories:

  • If \(x < 0\), then \(x\) cannot be split into the sum of \(k\) \(2^i\)s, because \(2^i > 0\), which obviously has no solution;
  • If the number of \(1\)s in the binary representation of \(x\) is greater than \(k\), there is also no solution in this case;
  • Otherwise, for the current \(k\), there must exist a splitting scheme.

Therefore, we start enumerating \(k\) from \(1\). Once we find a \(k\) that meets the condition, we can directly return the answer.

The time complexity is \(O(\log x)\), and the space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
        for k in count(1):
            x = num1 - k * num2
            if x < 0:
                break
            if x.bit_count() <= k <= x:
                return k
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int makeTheIntegerZero(int num1, int num2) {
        for (long k = 1;; ++k) {
            long x = num1 - k * num2;
            if (x < 0) {
                break;
            }
            if (Long.bitCount(x) <= k && k <= x) {
                return (int) k;
            }
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int makeTheIntegerZero(int num1, int num2) {
        using ll = long long;
        for (ll k = 1;; ++k) {
            ll x = num1 - k * num2;
            if (x < 0) {
                break;
            }
            if (__builtin_popcountll(x) <= k && k <= x) {
                return k;
            }
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func makeTheIntegerZero(num1 int, num2 int) int {
    for k := 1; ; k++ {
        x := num1 - k*num2
        if x < 0 {
            break
        }
        if bits.OnesCount(uint(x)) <= k && k <= x {
            return k
        }
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function makeTheIntegerZero(num1: number, num2: number): number {
    for (let k = 1; ; ++k) {
        let x = num1 - k * num2;
        if (x < 0) {
            break;
        }
        if (x.toString(2).replace(/0/g, '').length <= k && k <= x) {
            return k;
        }
    }
    return -1;
}

Comments