Question

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

English Version

题目描述

给你一个下标从 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$ 的数拆分为两个相等的数，这意味着操作后数组的元素和不会发生变化。因此，如果数组的元素和 $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$ 中的最大值。

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

class Solution {
  public int minOperations(List<Integer> nums, int target) {
    long s = 0;
    int[] cnt = new int[32];
    for (int x : nums) {
      s += x;
      for (int i = 0; i < 32; ++i) {
        if ((x >> i & 1) == 1) {
          ++cnt[i];
        }
      }
    }
    if (s < target) {
      return -1;
    }
    int i = 0, j = 0;
    int ans = 0;
    while (true) {
      while (i < 32 && (target >> i & 1) == 0) {
        ++i;
      }
      if (i == 32) {
        return ans;
      }
      while (j < i) {
        cnt[j + 1] += cnt[j] / 2;
        cnt[j] %= 2;
        ++j;
      }
      while (cnt[j] == 0) {
        cnt[j] = 1;
        ++j;
      }
      ans += j - i;
      --cnt[j];
      j = i;
      ++i;
    }
  }
}

class Solution {
public:
  int minOperations(vector<int>& nums, int target) {
    long long s = 0;
    int cnt[32]{};
    for (int x : nums) {
      s += x;
      for (int i = 0; i < 32; ++i) {
        if (x >> i & 1) {
          ++cnt[i];
        }
      }
    }
    if (s < target) {
      return -1;
    }
    int i = 0, j = 0;
    int ans = 0;
    while (1) {
      while (i < 32 && (target >> i & 1) == 0) {
        ++i;
      }
      if (i == 32) {
        return ans;
      }
      while (j < i) {
        cnt[j + 1] += cnt[j] / 2;
        cnt[j] %= 2;
        ++j;
      }
      while (cnt[j] == 0) {
        cnt[j] = 1;
        ++j;
      }
      ans += j - i;
      --cnt[j];
      j = i;
      ++i;
    }
  }
};

func minOperations(nums []int, target int) (ans int) {
  s := 0
  cnt := [32]int{}
  for _, x := range nums {
    s += x
    for i := 0; i < 32; i++ {
      if x>>i&1 > 0 {
        cnt[i]++
      }
    }
  }
  if s < target {
    return -1
  }
  var i, j int
  for {
    for i < 32 && target>>i&1 == 0 {
      i++
    }
    if i == 32 {
      return
    }
    for j < i {
      cnt[j+1] += cnt[j] >> 1
      cnt[j] %= 2
      j++
    }
    for cnt[j] == 0 {
      cnt[j] = 1
      j++
    }
    ans += j - i
    cnt[j]--
    j = i
    i++
  }
}

function minOperations(nums: number[], target: number): number {
  let s = 0;
  const cnt: number[] = Array(32).fill(0);
  for (const x of nums) {
    s += x;
    for (let i = 0; i < 32; ++i) {
      if ((x >> i) & 1) {
        ++cnt[i];
      }
    }
  }
  if (s < target) {
    return -1;
  }
  let [ans, i, j] = [0, 0, 0];
  while (1) {
    while (i < 32 && ((target >> i) & 1) === 0) {
      ++i;
    }
    if (i === 32) {
      return ans;
    }
    while (j < i) {
      cnt[j + 1] += cnt[j] >> 1;
      cnt[j] %= 2;
      ++j;
    }
    while (cnt[j] == 0) {
      cnt[j] = 1;
      j++;
    }
    ans += j - i;
    cnt[j]--;
    j = i;
    i++;
  }
}