What is the primary strategy for solving the Minimum Operations to Form Subsequence With Target Sum?

The primary strategy is to use a greedy approach combined with validation of invariants to minimize the number of operations while ensuring the subsequence sum matches the target.

What if the target sum is impossible to achieve?

If the target sum exceeds the total sum of all elements in the array, or if there is no combination of elements that can sum up to the target, the answer should be -1.

Can you use dynamic programming to solve this problem?

Although dynamic programming can be applied to similar problems, this problem can be more efficiently solved using greedy methods, leveraging powers of two for optimization.

How does bit manipulation play a role in solving this problem?

Bit manipulation allows for efficient management of powers of two and helps in optimizing the process of doubling smaller numbers to form the target sum.

How does GhostInterview help in solving this type of problem?

GhostInterview provides detailed step-by-step guidance, helping you understand the greedy approach, optimize operations, and avoid common pitfalls in achieving the target sum.

#2835

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

使子序列的和等于目标的最少操作次数

给你一个下标从 0 开始的数组 nums ，它包含非负整数，且全部为 2 的幂，同时给你一个整数 target 。一次操作中，你必须对数组做以下修改：选择数组中一个元素 nums[i] ，满足 nums[i] > 1 。将 nums[i] 从数组中删除。在 nums 的末尾添加两个…

数组贪心位运算

题目描述

给你一个下标从 0 开始的数组 nums ，它包含非负整数，且全部为 2 的幂，同时给你一个整数 target 。

一次操作中，你必须对数组做以下修改：

选择数组中一个元素 nums[i] ，满足 nums[i] > 1 。
将 nums[i] 从数组中删除。
在 nums 的末尾添加两个数，值都为 nums[i] / 2 。

你的目标是让 nums 的一个 子序列 的元素和等于 target ，请你返回达成这一目标的 最少操作次数 。如果无法得到这样的子序列，请你返回 -1 。

数组中一个 子序列 是通过删除原数组中一些元素，并且不改变剩余元素顺序得到的剩余数组。

示例 1：

输入：nums = [1,2,8], target = 7
输出：1
解释：第一次操作中，我们选择元素 nums[2] 。数组变为 nums = [1,2,4,4] 。
这时候，nums 包含子序列 [1,2,4] ，和为 7 。
无法通过更少的操作得到和为 7 的子序列。

示例 2：

输入：nums = [1,32,1,2], target = 12
输出：2
解释：第一次操作中，我们选择元素 nums[1] 。数组变为 nums = [1,1,2,16,16] 。
第二次操作中，我们选择元素 nums[3] 。数组变为 nums = [1,1,2,16,8,8] 。
这时候，nums 包含子序列 [1,1,2,8] ，和为 12 。
无法通过更少的操作得到和为 12 的子序列。

示例 3：

输入：nums = [1,32,1], target = 35
输出：-1
解释：无法得到和为 35 的子序列。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 2³⁰
nums 只包含非负整数，且均为 2 的幂。
1 <= target < 2³¹

lightbulb

解题思路

方法一：贪心 + 位运算

观察题目中的操作，我们发现，每次操作实际上是把一个大于 $1$ 的数拆分为两个相等的数，这意味着操作后数组的元素和不会发生变化。因此，如果数组的元素和 $s$ 小于 $target$ ，则无法通过题目描述的操作得到和为 $target$ 的子序列，直接返回 $-1$ 即可。否则，我们一定可以通过拆分操作，使得数组某个子序列的元素和等于 $target$ 。

另外，拆分操作实际上会把二进制高位为 $1$ 的数置为 $0$ ，并把低一位的数加上 $2$ 。因此，我们先用一个长度为 $32$ 的数组记录数组 $nums$ 所有元素的二进制表示中每个二进制位上 $1$ 的出现次数。

接下来，从 $target$ 的低位开始遍历，对于 $target$ 的第 $i$ 位，如果当前位数字为 $0$ ，则直接跳过，即 $i = i + 1$ 。如果当前位数字为 $1$ ，我们需要在数组 $cnt$ 中，找到最小的数字 $j$ （其中 $j \ge i$ ），使得 $cnt[j] \gt 0$ ，然后我们将该位的数字 $1$ 往低位 $i$ 拆分，即把 $cnt[j]$ 减 $1$ ，而 $cnt[i..j-1]$ 的每一位置为 $1$ ，操作次数为 $j-i$ 。接下来，我们令 $j = i$ ，然后 $i = i + 1$ 。重复上述操作，直到 $i$ 超出数组 $cnt$ 的下标范围，返回此时的操作次数。

注意，如果 $j \lt i$ ，实际上两个低位的 $1$ 可以合并成一个高一位的 $1$ 。因此，如果 $j \lt i$ ，我们将 $\frac{cnt[j]}{2}$ 加到 $cnt[j+1]$ 中，并将 $cnt[j]$ 取模 $2$ ，然后令 $j = j + 1$ ，继续上述操作。

时间复杂度 $O(n \times \log M)$ ，空间复杂度 $O(\log M)$ 。其中 $n$ 是数组 $nums$ 的长度，而 $M$ 是数组 $nums$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

class Solution:
    def minOperations(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if s < target:
            return -1
        cnt = [0] * 32
        for x in nums:
            for i in range(32):
                if x >> i & 1:
                    cnt[i] += 1
        i = j = 0
        ans = 0
        while 1:
            while i < 32 and (target >> i & 1) == 0:
                i += 1
            if i == 32:
                break
            while j < i:
                cnt[j + 1] += cnt[j] // 2
                cnt[j] %= 2
                j += 1
            while cnt[j] == 0:
                cnt[j] = 1
                j += 1
            ans += j - i
            cnt[j] -= 1
            j = i
            i += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates a solid understanding of greedy approaches and array manipulation.
question_mark
The candidate identifies the role of invariant validation to ensure correct results.
question_mark
The candidate balances time and space complexity considerations while optimizing the solution.

warning

常见陷阱

外企场景

error
Ignoring the constraints related to powers of two, which could lead to incorrect assumptions about the sequence's structure.
error
Failing to recognize when the target sum is impossible to achieve, such as when the sum of nums is smaller than the target.
error
Overcomplicating the solution by attempting to apply non-greedy methods when a greedy approach would suffice.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if nums contains negative powers of two?
arrow_right_alt
Can the solution be optimized for extremely large arrays, say nums.length > 1000?
arrow_right_alt
What happens if the target is much larger than the sum of the numbers in nums?

help

常见问题

外企场景

继续练习

#2871 将数组分割成最多数目的子数组 #2897 对数组执行操作使平方和最大 #2708 一个小组的最大实力值