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

给你一个下标从 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] <= 230
• nums 只包含非负整数，且均为 2 的幂。
• 1 <= target < 231

前置知识

请看 从集合论到位运算，常见位运算技巧分类总结！

思路

由于可以把一个数一分为二，所以整个数组可以全部变成 1。因此如果 nums 的元素和小于 target，则无解，返回 -1。否则一定有解。

然后从低位到高位贪心：

• 如果 target 的第 i 位是 0，跳过。
• 如果 target 的第 i 位是 1，那么先看看所有 \le 2^i 的元素和能否 \ge \textit{target}& \textit{mask，其中 mask}=2^{i+1}-1。如果能，那么必然可以合并出 target}& \textit{mask，无需操作（见 视频 中的证明）。
• 如果不能，那么就需要把一个更大的数（设它是 2^j）不断地一分为二，直到分解出 2^i 为止。
• 注意分解完后，2^i,2^{i+1},2^{i+2},\cdots,2^{j-1 这些 2 的幂我们都有了。所以后面 i+1,i+2,\cdots, j-1 这些比特位都无需判断了，可以直接从第 j 个比特位开始判断。

[sol-Python3]

class Solution:
    def minOperations(self, nums: List[int], target: int) -> int:
        if sum(nums) < target:
            return -1
        cnt = Counter(nums)
        ans = s = i = 0
        while 1 << i <= target:
            s += cnt[1 << i] << i
            mask = (1 << (i + 1)) - 1
            i += 1
            if s >= target & mask:
                continue
            ans += 1  # 一定要找更大的数操作
            while cnt[1 << i] == 0:
                ans += 1  # 还没找到，继续找更大的数
                i += 1
        return ans

[sol-Java]

class Solution {
    public int minOperations(List<Integer> nums, int target) {
        long s = 0;
        var cnt = new long[31];
        for (int x : nums) {
            s += x;
            cnt[Integer.numberOfTrailingZeros(x)]++;
        }
        if (s < target)
            return -1;
        int ans = 0, i = 0;
        s = 0;
        while ((1L << i) <= target) {
            s += cnt[i] << i;
            int mask = (int) ((1L << ++i) - 1);
            if (s >= (target & mask))
                continue;
            ans++; // 一定要找更大的数操作
            for (; cnt[i] == 0; i++)
                ans++; // 还没找到，继续找更大的数
        }
        return ans;
    }
}

[sol-C++]

class Solution {
public:
    int minOperations(vector<int> &nums, int target) {
        if (accumulate(nums.begin(), nums.end(), 0LL) < target)
            return -1;
        long long cnt[31]{};
        for (int x: nums)
            cnt[__builtin_ctz(x)]++;
        int ans = 0, i = 0;
        long long s = 0;
        while ((1LL << i) <= target) {
            s += cnt[i] << i;
            int mask = (1LL << ++i) - 1;
            if (s >= (target & mask))
                continue;
            ans++; // 一定要找更大的数操作
            for (; cnt[i] == 0; i++)
                ans++; // 还没找到，继续找更大的数
        }
        return ans;
    }
};

[sol-Go]

func minOperations(nums []int, target int) (ans int) {
	s := 0
	cnt := [31]int{}
	for _, v := range nums {
		s += v
		cnt[bits.TrailingZeros(uint(v))]++
	}
	if s < target {
		return -1
	}
	s = 0
	for i := 0; 1<<i <= target; {
		s += cnt[i] << i
		mask := 1<<(i+1) - 1
		if s >= target&mask {
			i++
			continue
		}
		ans++
		for i++; cnt[i] == 0; i++ {
			ans++
		}
	}
	return
}

复杂度分析

• 时间复杂度：\mathcal{O}(n+\log \textit{target})，其中 n 为 nums 的长度。
• 空间复杂度：\mathcal{O}(\log \textit{target})。