What is the main strategy to solve Minimum Operations to Make the Integer Zero?

Use bit manipulation combined with BFS or enumeration to subtract powers of 2 plus num2 until num1 reaches zero or detect impossibility.

Why is considering i up to 60 necessary?

Because 2^60 covers the largest possible num1 within constraints, ensuring no optimal operation is missed.

Can negative num1 values occur during operations?

Yes, intermediate negative values are possible and must be tracked to avoid invalid sequences or missed solutions.

How does num2 affect the minimum operation count?

num2 shifts all subtractions by a fixed amount, altering reachable states and potentially making some sequences impossible.

Is this problem purely a bit manipulation task?

No, it combines bit manipulation with a brainteaser pattern and careful enumeration to find the minimum operations.

#2749

Medium

auto_awesome位运算·操作·结合·brainteaser

LeetCode 题解工作台

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

给你两个整数： num1 和 num2 。在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2 i + num2 。请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。如果无法使 num1 等于 0 ，返回 -1 。示例 1： …

位运算脑筋急转弯枚举

题目描述

给你两个整数：num1 和 num2 。

在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2ⁱ + num2 。

请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。

如果无法使 num1 等于 0 ，返回 -1 。

示例 1：

输入：num1 = 3, num2 = -2
输出：3
解释：可以执行下述步骤使 3 等于 0 ：
- 选择 i = 2 ，并从 3 减去 2² + (-2) ，num1 = 3 - (4 + (-2)) = 1 。
- 选择 i = 2 ，并从 1 减去 2² + (-2) ，num1 = 1 - (4 + (-2)) = -1 。
- 选择 i = 0 ，并从 -1 减去 2⁰ + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。
可以证明 3 是需要执行的最少操作数。

示例 2：

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

提示：

1 <= num1 <= 10⁹
-10⁹ <= num2 <= 10⁹

lightbulb

解题思路

方法一：枚举

如果我们操作了 $k$ 次，那么问题实际上就变成了：判断 $\textit{num1} - k \times \textit{num2}$ 能否拆分成 $k$ 个 $2^i$ 之和。

我们不妨假设 $x = \textit{num1} - k \times \textit{num2}$ ，接下来分类讨论：

如果 $x \lt 0$ ，那么 $x$ 无法拆分成 $k$ 个 $2^i$ 之和，因为 $2^i \gt 0$ ，显然无解；
如果 $x$ 的二进制表示中 $1$ 的个数大于 $k$ ，此时也是无解；
否则，对于当前 $k$ ，一定存在一个拆分方案。

因此，我们从 $1$ 开始枚举 $k$ ，一旦找到一个满足条件的 $k$ ，就可以直接返回答案。

时间复杂度 $O(\log x)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
        for k in count(1):
            x = num1 - k * num2
            if x < 0:
                break
            if x.bit_count() <= k <= x:
                return k
        return -1

speed

复杂度分析

指标	值
时间	complexity depends on the number of states explored in BFS or enumeration, which can grow with the range of num1 and 2^i values. Space complexity is tied to storing visited states and the BFS queue.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for bit-level patterns in num1 that align with powers of 2 subtractions.
question_mark
Consider sequences where operations alternate between positive and negative deltas due to num2.
question_mark
Check for early impossibility to avoid unnecessary computation.

warning

常见陷阱

外企场景

error
Failing to handle negative intermediate values when subtracting 2^i + num2.
error
Ignoring the full range of i up to 60, which can miss optimal paths.
error
Overlooking scenarios where no sequence of operations can reach zero.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Restrict i to a smaller range, forcing tighter enumeration constraints.
arrow_right_alt
Change the fixed addition term num2 dynamically per operation.
arrow_right_alt
Require tracking the exact sequence of operations rather than just the minimum count.

help

常见问题

外企场景

继续练习

#2708 一个小组的最大实力值 #2568 最小无法得到的或值 #2959 关闭分部的可行集合数目