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

题目描述

给你两个整数：num1 和 num2 。

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

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

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

示例 1：

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

示例 2：

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

提示：

1 <= num1 <= 10⁹
-10⁹ <= num2 <= 10⁹

解法

方法一：枚举

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

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

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

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

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

Python3JavaC++GoTypeScript

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
}

function makeTheIntegerZero(num1: number, num2: number): number {
    for (let k = 1; ; ++k) {
        let x = num1 - k * num2;
        if (x < 0) {
            break;
        }
        if (x.toString(2).replace(/0/g, '').length <= k && k <= x) {
            return k;
        }
    }
    return -1;
}

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

题目描述

解法

方法一：枚举

评论