leetcode2749. 得到整数零需要执行的最少操作数-medium

1 题目：得到整数零需要执行的最少操作数

官方标定难度：中

给你两个整数：num1 和 num2 。

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

2 solution

如果 k 次可以完成的话则有：
$$nu{m}_1=\sum _{j=1}^k{2}^{i_j}+k\ast nu{m}_2$$
所以如果每次用 $nu{m}_1$ 减去 $nu{m}_2$ ，如果第 k 次剩余的数 m 能被 k 个2 的次方表示，则 k 就是答案。那怎么确定是否可以呢？这要求此时的 m 的二进制中最多有 k 个 1 并且 m 还要大于等于 k。

代码

class Solution {/** num1 = sum(2**i) + k * num2*/
public:int makeTheIntegerZero(int num1, int num2) {long long y = num1;for (int i = 1;; i++) {y -= num2;if (y < i) return -1;long long x = y;int c = 0;for (; x; x >>= 1) c += x & 1;if (c <= i && c ) return i;}}
};

结果