Minimum Operations to Form Subsequence With Target Sum

Hard
1471.

Minimum Operations to Form Subsequence With Target Sum

Minimum Operations to Form Subsequence With Target Sum is a hard coding problem on arrays, greedy and bit manipulation, asked in Amazon and Google interviews.

You are given an array nums of powers of two and an integer target. In one operation you pick an element nums[i] > 1, remove it, and append two copies of nums[i] / 2 to the end of the array.

Return the minimum number of operations after which nums has a subsequence whose elements sum to target, or -1 if that can never happen.

Example 1

Input
nums = [16,1], target = 6
Output
3
Explanation
Split 16 → 8, 8; split an 8 → 4, 4; split a 4 → 2, 2. Now 4 + 2 = 6.

Example 2

Input
nums = [4,1,1], target = 3
Output
1
Explanation
Split the 4 into two 2s, then take 2 + 1.

Example 3

Input
nums = [8], target = 9
Output
-1
Explanation
The total is only 8.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 2^30
  • nums consists only of non-negative powers of two
  • 1 <= target < 2^31
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var minOperations = function(nums, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Operations to Form Subsequence With Target Sum Solution

Minimum Operations to Form Subsequence With Target Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Operations to Form Subsequence With Target Sum is a hard coding problem on arrays, greedy and bit manipulation, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Greedy, Bit Manipulation
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array nums of powers of two and an integer target. In one operation you pick an element nums[i] > 1, remove it, and append two copies of nums[i] / 2 to the end of the array.

Return the minimum number of operations after which nums has a subsequence whose elements sum to target, or -1 if that can never happen.

Example 1

Input: nums = [16,1], target = 6
Output: 3
Explanation: Split 16 → 8, 8; split an 8 → 4, 4; split a 4 → 2, 2. Now 4 + 2 = 6.

Example 2

Input: nums = [4,1,1], target = 3
Output: 1
Explanation: Split the 4 into two 2s, then take 2 + 1.

Example 3

Input: nums = [8], target = 9
Output: -1
Explanation: The total is only 8.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 2^30
  • nums consists only of non-negative powers of two
  • 1 <= target < 2^31

Hints for Minimum Operations to Form Subsequence With Target Sum

  1. Hint 1

    Splitting never changes the total, so if sum(nums) < target the answer is -1; otherwise an answer always exists.

  2. Hint 2

    Since a subsequence may take elements in any positions, only the count of each power matters. Go through the bits of target from the lowest.

  3. Hint 3

    Small pieces can combine: two leftover 2^b act as one 2^(b+1). When a needed bit has nothing available, split the nearest larger power down to it, costing one operation per level.

How to solve Minimum Operations to Form Subsequence With Target Sum

Work bit by bit from the least significant. Keep counts of each power; unused small powers pair up to serve higher bits for free, and when a bit of target cannot be covered, break the smallest larger power — that costs exactly the number of levels it descends.

Approach

  1. If sum(nums) < target, return -1 (use 64-bit for the sum).
  2. Count cnt[b], the number of elements equal to 2^b.
  3. For b from 0 to 30: if bit b of target is set, use one 2^b if cnt[b] > 0; otherwise find the smallest j > b with cnt[j] > 0, add j - b to the answer, decrement cnt[j], and add one to each cnt[b] .. cnt[j - 1] (splitting leaves one spare at each level, and the second 2^b is the one used).
  4. Then carry: cnt[b + 1] += cnt[b] / 2, since two unused 2^b sum to 2^(b+1).
  5. Return the total.

Why it works

Low bits of target can only be formed from equally low or lower powers, so it is safe to settle them first, and merging two spare 2^b into a virtual 2^(b+1) loses nothing. When a bit is missing, some larger power must be split at least down to that level; splitting the smallest available one costs the fewest operations and leaves spares (2^b … 2^(j-1)) that only help later bits.

Complexity

  • Time — O(n + 31^2)
  • Space — O(31)

Pitfalls

  • The sum of nums can exceed 32 bits — check feasibility with 64-bit arithmetic.
  • Carry the leftover counts upward after handling each bit; otherwise pairs of small powers are wasted.
  • Count one operation per halving level (j - b), not one per split power.

Reference solution

Python

from typing import List

def minOperations(nums: List[int], target: int) -> int:
    if sum(nums) < target:
        return -1
    cnt = [0] * 64
    for v in nums:
        cnt[v.bit_length() - 1] += 1
    ops = 0
    for b in range(31):
        if target >> b & 1:
            if cnt[b] > 0:
                cnt[b] -= 1
            else:
                j = b
                while cnt[j] == 0:
                    j += 1
                ops += j - b
                cnt[j] -= 1
                for t in range(b, j):
                    cnt[t] += 1
        cnt[b + 1] += cnt[b] // 2
    return ops

Java

public static int minOperations(int[] nums, int target) {
    long sum = 0;
    long[] cnt = new long[64];
    for (int v : nums) {
        sum += v;
        cnt[31 - Integer.numberOfLeadingZeros(v)]++;
    }
    if (sum < target) return -1;
    int ops = 0;
    for (int b = 0; b < 31; b++) {
        if (((target >> b) & 1) == 1) {
            if (cnt[b] > 0) cnt[b]--;
            else {
                int j = b;
                while (cnt[j] == 0) j++;
                ops += j - b;
                cnt[j]--;
                for (int t = b; t < j; t++) cnt[t]++;
            }
        }
        cnt[b + 1] += cnt[b] / 2;
    }
    return ops;
}

C++

int minOperations(vector<int>& nums, int target) {
    long long sum = 0;
    vector<long long> cnt(64, 0);
    for (int v : nums) {
        sum += v;
        cnt[31 - __builtin_clz((unsigned)v)]++;
    }
    if (sum < target) return -1;
    int ops = 0;
    for (int b = 0; b < 31; b++) {
        if ((target >> b) & 1) {
            if (cnt[b] > 0) cnt[b]--;
            else {
                int j = b;
                while (cnt[j] == 0) j++;
                ops += j - b;
                cnt[j]--;
                for (int t = b; t < j; t++) cnt[t]++;
            }
        }
        cnt[b + 1] += cnt[b] / 2;
    }
    return ops;
}

JavaScript

var minOperations = function(nums, target) {
    var cnt = new Array(64).fill(0);
    var sum = 0;
    for (var i = 0; i < nums.length; i++) {
        sum += nums[i];
        cnt[31 - Math.clz32(nums[i])]++;
    }
    if (sum < target) return -1;
    var ops = 0;
    for (var b = 0; b < 31; b++) {
        if ((target >> b) & 1) {
            if (cnt[b] > 0) cnt[b]--;
            else {
                var j = b;
                while (cnt[j] === 0) j++;
                ops += j - b;
                cnt[j]--;
                for (var t = b; t < j; t++) cnt[t]++;
            }
        }
        cnt[b + 1] += Math.floor(cnt[b] / 2);
    }
    return ops;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms