Question

2749. 得到整数零需要执行的最少操作数

English Version

题目描述

给你两个整数：num1 和 num2 。

在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2i + num2 。

请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。

如果无法使 num1 等于 0 ，返回 -1 。

 

示例 1：

输入：num1 = 3, num2 = -2
输出：3
解释：可以执行下述步骤使 3 等于 0 ：
- 选择 i = 2 ，并从 3 减去 22 + (-2) ，num1 = 3 - (4 + (-2)) = 1 。
- 选择 i = 2 ，并从 1 减去 22 + (-2) ，num1 = 1 - (4 + (-2)) = -1 。
- 选择 i = 0 ，并从 -1 减去 20 + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。
可以证明 3 是需要执行的最少操作数。

示例 2：

输入：num1 = 5, num2 = 7
输出：-1
解释：可以证明，执行操作无法使 5 等于 0 。

 

提示：

• 1 <= num1 <= 109
• -109 <= num2 <= 109

解法

方法一：枚举

如果我们操作了 $k$ 次，那么问题实际上就变成了：判断 $num1 - k \times num2$ 能否拆分成 $k$ 个 $2^i$ 之和。

我们不妨假设 $x = num1 - k \times num2$，接下来分类讨论：

• 如果 $x \lt 0$，那么 $x$ 无法拆分成 $k$ 个 $2^i$ 之和，因为 $2^i \gt 0$，显然无解；
• 如果 $x$ 的二进制表示中 $1$ 的个数大于 $k$，此时也是无解；
• 否则，对于当前 $k$，一定存在一个拆分方案。

因此，我们从 $1$ 开始枚举 $k$，一旦找到一个满足条件的 $k$，就可以直接返回答案。

时间复杂度 $O(\log x)$，空间复杂度 $O(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
}