题目

给你两个整数：num1 和 num2 。

在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2^i + 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 <= 10^9
-10^9 <= num2 <= 10^9

解题思路

首先，我们对原等式进行变换： $$num1 - (2^{i_1} + num2) - (2^{i_2} + num2) - ... - (2^{i_k} + num2) = 0$$

将所有 num2 移项，得到： $$num1 - k * num2 = 2^{i_1} + 2^{i_2} + ... + 2^{i_k}$$

其中 k 是操作次数，也是我们需要求的最小值。

这个等式告诉我们，num1 - k * num2 必须可以表示为 k 个 2 的幂的和。

贪心算法

一个直观的想法是，每次都尽可能选择最大的 2^i 来减去，这样可以更快地接近 0。但这个方法在这里并不适用，因为它没有考虑到 k 个 num2 的和，k 是未知数。

正确的解题思路是，我们枚举操作次数 k，从 1 开始，直到找到第一个满足条件的 k。

具体

处理 num2 的正负情况
- 如果 num2 是正数，那么每次操作 num1 都会减去 2^i + num2，这个值总是大于 0。如果 num1 本身就是正数，那么 num1 只会越来越小。如果 num1 - k * num2 在某一步骤变为负数，那么 num1 将永远无法变成 0。我们需要确保 num1 - k * num2 始终是非负数，并且可以被表示为 k 个 2 的幂的和。
- 如果 num2 是负数，那么每次操作 num1 都会减去 2^i 并加上一个正数 |num2|。这意味着 num1 可能增加也可能减少。
枚举操作次数 k
- 我们从 k = 1 开始，递增地尝试。对于每一个 k，计算 target = num1 - k * num2。
- 如果 target < k，则 target 无法表示为 k 个 2 的幂的和，因为每个 2^i 至少是 1 (2^0)。继续尝试下一个 k。
- 如果 target 是一个负数，并且 num2 是正数，那么 num1 永远无法变成 0。因为 num1 会一直减小，不可能再变回 0。
- 对于 target >= k 的情况，我们需要判断 target 是否可以表示成 k 个 2 的幂的和。这可以通过检查 target 的二进制表示来完成。
检查 target 的二进制表示
- target 可以表示成 k 个 2 的幂的和，等价于 target 的二进制表示中，1 的个数（也叫 popcount 或 hamming weight）小于等于 k。
- 为什么？因为任何一个正整数都可以唯一地表示成若干个不重复的 2 的幂的和（即它的二进制表示）。例如，13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0。13 的二进制是 1101，有 3 个 1。这表示 13 最少需要 3 个 2 的幂的和。
- 如果 target 的 popcount 记为 p，那么 target 可以表示为 p 个 2 的幂的和。
- 我们还可以通过拆分 2^i 来增加项数。例如，2^3 可以拆分成 2^2 + 2^2，这样就增加了 1 项。所以，如果 target 的 popcount 是 p，它就可以表示为 p 个、p+1 个、p+2 个... 的 2 的幂的和。
- 所以，我们只需要判断 p <= k 且 target >= k 是否成立，公式如下：$$\mathrm{popcount}(t)\leq m\leq t$$
循环与终止条件
- 我们从 k = 1 开始循环。
- 如果 k 递增到某个值，使得 num1 - k * num2 成为一个非常大的负数（例如，num1 - k*num2 < -60），且 num2 是正数，那么我们就可以停止循环并返回 -1。因为 num1 - k*num2 变得越来越小，不满足 target >= k。一个更严谨的判断是 num1 - k*num2 什么时候会小于 k。
- 当 k 满足 (num1 - k*num2) >= k 且 popcount(num1 - k*num2) <= k 时，我们找到了最小的操作次数，返回 k。
- 如果 k 循环到 60 仍然没有找到，num1 - k * num2 可能会溢出 long long 的范围。但题目给出的 i 范围是 [0, 60]，这意味着我们最多可以使用 60 个 2 的幂，即 2^60。一个稳健的办法是设定一个循环上限，例如 k 循环到 60 左右，如果还没有结果，可能就无法达成。更严谨的上限可以根据 num1 和 num2 的值来推导。当 k 足够大时，num1 - k*num2 可能会远小于 k，此时可以停止。

具体代码

class Solution {
public:
    int makeTheIntegerZero(int num1, int num2) {

        for(int k = 0; k <= 32; k++)
        {
            long long current = num1 - 1LL * k * num2;
            if(current >= k)
            {
                int count = 0;
                while(current > 0) // 这里的运算取巧
                {
                    current &= current - 1;
                    count++;
                }
                
                if(count <= k)
                    return k;
            }
        }

        return -1;
    }
};

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

beautifulremi

题目

解题思路

贪心算法

具体

具体代码