LeetCode Record – 5 得到整数零需要执行的最少操作数

25 – 09 – 05 (补于 25 – 09 – 09)

沟槽的 CUMCM 2025 A，45维的优化是人干的事？还是 LeetCode 可爱

题面：

给你两个整数：num1 和 num2 。

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

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

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

很独特的一道题，开始以为是构造于是浅推了一下。

原表达式可转换为：

$$\text{num}_1 -\ \text{num}_2\cdot K^T = \sum\limits_{i = 1}^{\text{Sizeof}(K)}2^{k_i}\quad \quad \text{其中}K = [k_1,\dots, k_n]$$

所以问题相当于对 $\text{num}_1$ 进行 $k$ 次相减操作，考虑当前结果能否被表示为 $k$ 个 2 的 $i$ 次幂和,其中 $i\in[0,60]$

因此这相当于是一道位运算题，统计 $\text{res} = \text{num}_1 – \text{num}_2$ 的 1 的数量是否小于当前次数 $\text{Sizeof}(K)$，因为对于大于的情况，我们总能通过降一级换两个的方式满足 $k$

所以实现代码其实不长：

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

以上