题目描述
给你两个整数:num1
和 num2
。
在一步操作中,你需要从范围 [0, 60]
中选出一个整数 i
,并从 num1
减去 2^i + num2
。
请你计算,要想使 num1
等于 0
需要执行的最少操作数,并以整数形式返回。
如果无法使 num1
等于 0
,返回 -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 是需要执行的最少操作数。
输入:num1 = 5, num2 = 7
输出:-1
解释:可以证明,执行操作无法使 5 等于 0。
限制
1 <= num1 <= 10^9
-10^9 <= num2 <= 10^9
算法
(思维题) $O(60 \log num1)$
- 从 $1$ 开始枚举答案,假设最终的操作次数为 $ans$,判定是否可行。
- 操作次数为 $ans$ 时,$num1$ 需要额外减去 $ans \cdot num2$ 的值,然后判定 $num1$ 是否可以通过恰好 $ans$ 次 $2$ 的幂次累加得到。
- 假设 $num1$ 的二进制位上的 $1$ 为 $c$ 个,则当 $c \le ans \le num1$ 时,可以通过恰好 $ans$ 次 $2$ 的幂次累加得到,累加答案。
- 当发现 $num1 < ans$ 时,则直接退出返回 $-1$。
时间复杂度
- 最坏情况下,只需要最多枚举 $60$ 轮左右就可以得到答案。
- 每一轮枚举需要 $O(\log num1)$ 的时间。
- 故总时间复杂度为 $O(60 \log num1)$。
空间复杂度
- 进需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
private:
int get_one(LL x) {
int cnt = 0;
for(; x; x -= x & -x)
++cnt;
return cnt;
}
public:
int makeTheIntegerZero(int num1, int num2) {
LL x = num1;
int ans = 0;
while (1) {
++ans;
x -= num2;
if (x < ans)
break;
if (ans >= get_one(x))
return ans;
}
return -1;
}
};