README.md

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

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

时间复杂度 $O(\log x)$，空间复杂度 $O(1)$。

Python3

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

Java

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

C++

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

Go

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
}

...