Minimum operations to form subsequence with target sum

Array Greedy Bit Manipulation

32.4% acceptance

Feb 25, 2026

554

128

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.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(nums: Vec<i32>, target: i32) -> i32 {
    let target = target as i64;
    let total: i64 = nums.iter().map(|&x| x as i64).sum();
    if total < target { return -1; }
    let mut cnt = [0i64; 32];
    for &x in &nums { cnt[x.trailing_zeros() as usize] += 1; }
    let mut ops = 0i32;
    for bit in 0..31usize {
      if (target >> bit) & 1 == 1 {
        if cnt[bit] > 0 {
          cnt[bit] -= 1;
        } else {
          // Find smallest j > bit with cnt[j] > 0
          for j in (bit + 1)..32 {
            if cnt[j] > 0 {
              ops += (j - bit) as i32;
              cnt[j] -= 1;
              for k in bit..j { cnt[k] += 1; }
              cnt[bit] -= 1; // use the generated element
              break;
            }
          }
        }
      }
      // Carry excess pairs upward
      if bit + 1 < 32 { cnt[bit + 1] += cnt[bit] / 2; }
    }
    ops
  }
}