title
给你一个下标从 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 <= 10001 <= nums[i] <= 230nums只包含非负整数，且均为 2 的幂。1 <= target < 231
solution
只要我们的target不超过数组所有数的和，那么我们一定可以使用数组进行操作对其表示。
贪心实现。枚举每一个位所需。
class Solution:
def minOperations(self, nums: List[int], target: int) -> int:
if sum(nums) < target:
return -1
left_sum = 0
ans = 0
counter = collections.Counter(nums)
for i in range(31):
left_sum += counter[1 << i] << i
if (1 << i) & target == 0:
continue
# 贪心 减去当前位的
left_sum -= 1 << i
# 左边已经够了
# print(left_sum)
if left_sum >= 0:
continue
for j in range(i + 1, 31):
if counter[1 << j]:
ans += j - i
counter[1 << j] -= 1
left_sum += 1 << j
break
return ans