Question

2835. Minimum Operations to Form Subsequence With Target Sum

中文文档

Description

You are given a 0-indexed array nums consisting of non-negative powers of 2, and an integer target.

In one operation, you must apply the following changes to the array:

• Choose any element of the array nums[i] such that nums[i] > 1.
• Remove nums[i] from the array.
• Add two occurrences of nums[i] / 2 to the end of nums.

Return the _minimum number of operations you need to perform so that _nums_ contains a subsequence whose elements sum to_ target. If it is impossible to obtain such a subsequence, return -1.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

 

Example 1:

Input: nums = [1,2,8], target = 7
Output: 1
Explanation: In the first operation, we choose element nums[2]. The array becomes equal to nums = [1,2,4,4].
At this stage, nums contains the subsequence [1,2,4] which sums up to 7.
It can be shown that there is no shorter sequence of operations that results in a subsequnce that sums up to 7.

Example 2:

Input: nums = [1,32,1,2], target = 12
Output: 2
Explanation: In the first operation, we choose element nums[1]. The array becomes equal to nums = [1,1,2,16,16].
In the second operation, we choose element nums[3]. The array becomes equal to nums = [1,1,2,16,8,8]
At this stage, nums contains the subsequence [1,1,2,8] which sums up to 12.
It can be shown that there is no shorter sequence of operations that results in a subsequence that sums up to 12.

Example 3:

Input: nums = [1,32,1], target = 35
Output: -1
Explanation: It can be shown that no sequence of operations results in a subsequence that sums up to 35.

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 230
• nums consists only of non-negative powers of two.
• 1 <= target < 231

Solutions

Solution 1: Greedy + Bit Manipulation

Observing the operation in the problem, we find that each operation actually splits a number greater than $1$ into two equal numbers, which means that the sum of the elements in the array will not change after the operation. Therefore, if the sum of the elements in the array $s$ is less than $target$, it is impossible to obtain a subsequence with a sum of $target$ through the operation described in the problem, and we can directly return $-1$. Otherwise, we can definitely make the sum of some subsequences in the array equal to $target$ through the split operation.

In addition, the split operation will actually set the binary high bit of the number to $0$ and add $2$ to the lower bit. Therefore, we first use an array of length $32$ to record the number of times $1$ appears on each binary bit in the binary representation of all elements in the array $nums$.

Next, starting from the low bit of $target$, for the $i$th bit of $target$, if the current bit number is $0$, skip it directly, that is, $i = i + 1$. If the current bit number is $1$, we need to find the smallest number $j$ (where $j \ge i$) in the array $cnt$ such that $cnt[j] > 0$, and then we split the number $1$ at this bit to the lower bit $i$, that is, subtract $1$ from $cnt[j]$, and set each bit from $i$ to $j-1$ in $cnt$ to $1$, and the number of operations is $j-i$. Next, we let $j = i$, and then $i = i + 1$. Repeat the above operation until $i$ exceeds the index range of the array $cnt$, and return the number of operations at this time.

Note that if $j < i$, actually two lower bits of $1$ can be combined into a higher bit of $1$. Therefore, if $j < i$, we add $\frac{cnt[j]}{2}$ to $cnt[j+1]$, and take $cnt[j]$ modulo $2$, then let $j = j + 1$, and continue the above operation.

The time complexity is $O(n \times \log M)$, and the space complexity is $O(\log M)$. Here, $n$ is the length of the array $nums$, and $M$ is the maximum value in the array $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++;
  }
}