Skip to content

Latest commit

 

History

History

2749

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 

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:

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