2749. Minimum Operations to Make the Integer Zero

Leetcode link

题目简介

本题更像是一道数学题，题目给了我们两个数字 num1 与 num2，要求我们用 num1 减去多次 $2^i + num2$ 直到最终结果为 0

其中 i 的范围是 $0 \le i \le 60$

解题思路

要解答这一题我们需要一些数学推导，推导前我们需要一些符号来简化描述：

• a 代表题目中的 num1

• b 代表题目中的 num2

• t 代表减去 $2^i + num2$ 的次数

• c 代表一连串 2 的次方的和

下面进入推导： 有了 c，我们能很容易得出 2 的次方的个数，只要将 c 转换成二进制然后看看有几个 1 就好，这个个数我们使用 x 来代替

有了上述信息，我们可以给 t 一个范围

• $x \le t$：x 有可能小于 t 是因为会出现类似 $2^0 + 2^0 = 2^1$ 的情况，这种情况下我们只会算一个 1
• $t \le c$：在所有的 i 都为 0 的情况，t === c，否则 c > t

综上，我们得到 $x \le t \le c$ 的范围

接下来我们只需要在 0～60 的范围里面由小到大循环 i，直到找到符合上述范围的 i 就是我们的答案了

Javascript

/**
 * @param {number} num1
 * @param {number} num2
 * @return {number}
 */
var makeTheIntegerZero = function (num1, num2) {
    const countOneInBits = num => num.toString(2).replace(/0/g, '').length

    for (let i = 1; i <= 60; i++) {
        const sumOfTwoPower = num1 - i * num2
        const oneInSumOfTwoPower = countOneInBits(sumOfTwoPower)

        if(i > sumOfTwoPower) {
            return -1
        }
        if(i >= oneInSumOfTwoPower) {
            return i
        }
    }

    return -1
};