Medium

题目描述

给你两个整数 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 中减去 2^2 + (-2) = 4 + (-2) = 2，得到 3 - 2 = 1
- 选择 i = 2，从 1 中减去 2^2 + (-2) = 4 + (-2) = 2，得到 1 - 2 = -1
- 选择 i = 0，从 -1 中减去 2^0 + (-2) = 1 + (-2) = -1，得到 (-1) - (-1) = 0
可以证明，3 是我们需要执行的最少操作次数。

示例 2：

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

约束条件：

  • 1 <= num1 <= 10^9
  • -10^9 <= num2 <= 10^9

解题思路

这道题的核心思想是枚举操作次数，然后检查是否可行。

首先分析问题：我们需要进行 k 次操作，每次操作减去 2^i + num2，最终使 num1 变为 0。设操作次数为 k，那么：

num1 - k * num2 - (2^i1 + 2^i2 + ... + 2^ik) = 0

即：2^i1 + 2^i2 + ... + 2^ik = num1 - k * num2

设 target = num1 - k * num2，问题转化为：能否选择 k 个 2 的幂次（可以重复）使其和等于 target？

关键观察：

  1. 如果 target <= 0，显然不可能（2的幂次都是正数）
  2. 最少需要 popcount(target) 次操作（target 的二进制中 1 的个数）
  3. 最多需要 target 次操作（全选择 2^0 = 1）
  4. 因此，可行的充要条件是：popcount(target) <= k <= target

算法流程：

  1. 从 k = 1 开始枚举操作次数
  2. 计算 target = num1 - k * num2
  3. 检查是否满足 popcount(target) <= k <= target
  4. 如果满足则返回 k，否则继续
  5. 由于最多 60 次操作，超过则返回 -1

代码实现

class Solution {
public:
    int makeTheIntegerZero(int num1, int num2) {
        for (int k = 1; k <= 60; k++) {
            long long target = (long long)num1 - (long long)k * num2;
            if (target <= 0) continue;
            if (__builtin_popcountll(target) <= k && k <= target) {
                return k;
            }
        }
        return -1;
    }
};

class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
        for k in range(1, 61):
            target = num1 - k * num2
            if target <= 0:
                continue
            if bin(target).count('1') <= k <= target:
                return k
        return -1

public class Solution {
    public int MakeTheIntegerZero(int num1, int num2) {
        for (int k = 1; k <= 60; k++) {
            long target = (long)num1 - (long)k * num2;
            if (target <= 0) continue;
            int popcount = System.Numerics.BitOperations.PopCount((ulong)target);
            if (popcount <= k && k <= target) {
                return k;
            }
        }
        return -1;
    }
}

var makeTheIntegerZero = function(num1, num2) {
    const popcount = (n) => {
        let count = 0;
        while (n > 0) {
            count += n & 1;
            n >>>= 1;
        }
        return count;
    };
    
    for (let k = 1; k <= 60; k++) {
        const target = num1 - k * num2;
        if (target <= 0) continue;
        if (popcount(target) <= k && k <= target) {
            return k;
        }
    }
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(60 × log(target)) = O(log(num1))
空间复杂度O(1)

说明：

  • 枚举操作次数最多 60 次
  • 每次计算 popcount 的时间复杂度为 O(log(target))
  • 空间复杂度为常数级别

相关题目