class Solution {
public:
int makeTheIntegerZero(int num1, int num2) {
}
};
6471. 得到整数零需要执行的最少操作数
给你两个整数：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原站题解
java 解法, 执行用时: 0 ms, 内存消耗: 38.5 MB, 提交时间: 2023-06-26 09:17:28
class Solution {
public int makeTheIntegerZero(int num1, int num2) {
for (long k = 1; k <= num1 - num2 * k; k++)
if (k >= Long.bitCount(num1 - num2 * k))
return (int) k;
return -1;
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 5.8 MB, 提交时间: 2023-06-26 09:17:14
class Solution {
public:
int makeTheIntegerZero(int num1, int num2) {
for (long long k = 1; k <= num1 - num2 * k; k++)
if (k >= __builtin_popcountll(num1 - num2 * k))
return k;
return -1;
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-06-26 09:16:55
func makeTheIntegerZero(num1, num2 int) int {
for k := 1; k <= num1-num2*k; k++ {
if k >= bits.OnesCount(uint(num1-num2*k)) {
return k
}
}
return -1
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-26 09:16:43
class Solution:
def makeTheIntegerZero(self, num1: int, num2: int) -> int:
import itertools
for k in itertools.count(1):
x = num1 - num2 * k
if x < k: return -1
if k >= x.bit_count(): return k