Skip to content

2835. Minimum Operations to Form Subsequence With Target Sum 👍

  • Time: $O(n)$
  • Space: $O(31) = O(1)$
 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
31
32
33
34
35
36
37
class Solution {
 public:
  int minOperations(vector<int>& nums, int target) {
    constexpr int kNoMissingBit = 31;
    constexpr int maxBit = 31;
    int ans = 0;
    int minMissingBit = kNoMissingBit;
    // count[i] := the number of occurrences of 2^i
    vector<int> count(maxBit + 1);

    for (const int num : nums)
      ++count[static_cast<int>(log2(num))];

    for (int bit = 0; bit < maxBit; ++bit) {
      // Check if `bit` is in the target.
      if (target >> bit & 1) {
        // If there are available bits, use one bit.
        if (count[bit] > 0)
          --count[bit];
        else
          minMissingBit = min(minMissingBit, bit);
      }
      // If we previously missed a bit and there are available bits.
      if (minMissingBit != kNoMissingBit && count[bit] > 0) {
        --count[bit];
        // Count the operations to break `bit` into `minMissingBit`.
        ans += bit - minMissingBit;
        minMissingBit = kNoMissingBit;
      }
      // Combining smaller numbers costs nothing.
      count[bit + 1] += count[bit] / 2;
    }

    // Check if all target bits have been covered, otherwise return -1.
    return minMissingBit == kNoMissingBit ? ans : -1;
  }
};

 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
31
32
33
34
35
36
public class Solution {
  public int minOperations(List<Integer> nums, int target) {
    final int kNoMissingBit = 31;
    final int maxBit = 31;
    int ans = 0;
    int minMissingBit = kNoMissingBit;
    // count[i] := the number of occurrences of 2^i
    int[] count = new int[maxBit + 1];

    for (final int num : nums)
      ++count[(int) (Math.log(num) / Math.log(2))];

    for (int bit = 0; bit < maxBit; ++bit) {
      // Check if `bit` is in the target.
      if ((target >> bit & 1) == 1) {
        // If there are available bits, use one bit.
        if (count[bit] > 0)
          --count[bit];
        else
          minMissingBit = Math.min(minMissingBit, bit);
      }
      // If we previously missed a bit and there are available bits.
      if (minMissingBit != kNoMissingBit && count[bit] > 0) {
        --count[bit];
        // Count the operations to break `bit` into `minMissingBit`.
        ans += bit - minMissingBit;
        minMissingBit = kNoMissingBit; // Set it to an the invalid value.
      }
      // Combining smaller numbers costs nothing.
      count[bit + 1] += count[bit] / 2;
    }

    // Check if all target bits have been covered, otherwise return -1.
    return minMissingBit == kNoMissingBit ? ans : -1;
  }
}

 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
class Solution:
  def minOperations(self, nums: list[int], target: int) -> int:
    kNoMissingBit = 31
    maxBit = 31
    ans = 0
    minMissingBit = kNoMissingBit
    # count[i] := the number of occurrences of 2^i
    count = collections.Counter(int(math.log2(num)) for num in nums)

    for bit in range(maxBit):
      # Check if `bit` is in the target.
      if target >> bit & 1:
        # If there are available bits, use one bit.
        if count[bit] > 0:
          count[bit] -= 1
        else:
          minMissingBit = min(minMissingBit, bit)
      # If we previously missed a bit and there are available bits.
      if minMissingBit != kNoMissingBit and count[bit] > 0:
        count[bit] -= 1
        # Count the operations to break `bit` into `minMissingBit`.
        ans += bit - minMissingBit
        minMissingBit = kNoMissingBit  # Set it to an the invalid value.
      # Combining smaller numbers costs nothing.
      count[bit + 1] += count[bit] // 2

    # Check if all target bits have been covered, otherwise return -1.
    return ans if minMissingBit == maxBit else -1