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

Thinking

Each step subtracts \(2^i+num2\) from \(num1\); we want the fewest steps that reach \(0\). The exponent range is large, so searching the sequence of \(i\) is impossible.

After exactly \(k\) operations, \(x=num1-k\cdot num2\) must be a sum of \(k\) powers of two, i.e. \(x\ge k\) and the popcount of \(x\) is at most \(k\). Increase \(k\) from \(1\) and stop once \(x\) becomes negative.

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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn make_the_integer_zero(num1: i32, num2: i32) -> i32 {
        let num1 = num1 as i64;
        let num2 = num2 as i64;
        for k in 1.. {
            let x = num1 - k * num2;
            if x < 0 {
                break;
            }
            if (x.count_ones() as i64) <= k && k <= x {
                return k as i32;
            }
        }
        -1
    }
}

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

Comments