What is the best approach for Minimum Operations to Reduce an Integer to 0?

A state transition dynamic programming approach combined with bit manipulation is optimal, ensuring minimal operations by simulating all reachable states efficiently.

Can I solve this using only greedy strategies?

Greedy bit flipping helps, but without DP, it may miss sequences that reduce n in fewer operations.

How does bit manipulation help reduce operations?

Examining binary representation identifies which powers of two to add or subtract, preventing unnecessary moves and aligning with optimal DP states.

What are common mistakes when implementing this problem?

Ignoring addition operations, over-expanding states, or not considering higher-order bit flips can all lead to suboptimal solutions.

Does this problem have a strict time constraint?

Yes, naive exploration of all possible powers without DP or bit optimization can be too slow for larger n.

#2571

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

将整数减少到零需要的最少操作数

给你一个正整数 n ，你可以执行下述操作任意次： n 加上或减去 2 的某个幂返回使 n 等于 0 需要执行的最少操作数。如果 x == 2 i 且其中 i >= 0 ，则数字 x 是 2 的幂。示例 1：输入： n = 39 输出： 3 解释：我们可以执行下述操作： - n 加…

动态规划贪心位运算

题目描述

给你一个正整数 n ，你可以执行下述操作任意次：

n 加上或减去 2 的某个幂

返回使 n 等于 0 需要执行的最少操作数。

如果 x == 2ⁱ 且其中 i >= 0 ，则数字 x 是 2 的幂。

示例 1：

输入：n = 39
输出：3
解释：我们可以执行下述操作：
- n 加上 2⁰ = 1 ，得到 n = 40 。
- n 减去 2³ = 8 ，得到 n = 32 。
- n 减去 2⁵ = 32 ，得到 n = 0 。
可以证明使 n 等于 0 需要执行的最少操作数是 3 。

示例 2：

输入：n = 54
输出：3
解释：我们可以执行下述操作：
- n 加上 2¹ = 2 ，得到 n = 56 。
- n 加上 2³ = 8 ，得到 n = 64 。
- n 减去 2⁶ = 64 ，得到 n = 0 。
使 n 等于 0 需要执行的最少操作数是 3 。

提示：

1 <= n <= 10⁵

lightbulb

解题思路

方法一：贪心 + 位运算

我们将整数 $n$ 转换为二进制，从最低位开始：

如果当前位为 $1$ ，我们就累加当前连续的 $1$ 的个数；
如果当前位为 $0$ ，我们就判断当前连续的 $1$ 的个数是否超过 $0$ 。如果是，判断当前连续的 $1$ 的个数是否为 $1$ ，如果是，说明我们通过一次操作可以消除 $1$ ；如果大于 $1$ ，说明我们通过一次操作，可以把连续的 $1$ 的个数减少到 $1$ 。

最后，我们还需要判断当前连续的 $1$ 的个数是否为 $1$ ，如果是，说明我们通过一次操作可以消除 $1$ ；如果大于 $1$ ，我们通过两次操作，可以把连续的 $1$ 的消除。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为题目给定的整数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def minOperations(self, n: int) -> int:
        ans = cnt = 0
        while n:
            if n & 1:
                cnt += 1
            elif cnt:
                ans += 1
                cnt = 0 if cnt == 1 else 1
            n >>= 1
        if cnt == 1:
            ans += 1
        elif cnt > 1:
            ans += 2
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on the chosen approach; naive BFS can be O(n log n) due to powers of two exploration, while optimized DP with bit manipulation reduces redundant states. Space complexity is dominated by the number of states tracked in DP.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They may hint at using binary representation to simplify operations.
question_mark
Expect discussion of state transition or dynamic programming strategy.
question_mark
Watch for opportunities to combine greedy bit-level optimization with DP.

warning

常见陷阱

外企场景

error
Attempting only subtraction without considering additions of powers of two.
error
Not limiting state expansion leads to excessive memory usage.
error
Ignoring the benefit of flipping higher-order bits for faster reduction.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Minimize operations when only subtraction of powers of two is allowed.
arrow_right_alt
Find maximum integer reachable within k operations of powers of two.
arrow_right_alt
Count distinct sequences of operations that reduce n to zero.

help

常见问题

外企场景

继续练习

#2708 一个小组的最大实力值 #3068 最大节点价值之和 #2572 无平方子集计数