Question

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

Solutions

Solution 1

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

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

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

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
}