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 <= 10001 <= nums[i] <= 2^30nums consists only of non-negative powers of two1 <= target < 2^31
Hints for Minimum Operations to Form Subsequence With Target Sum
Hint 1
Splitting never changes the total, so if
sum(nums) < targetthe answer is-1; otherwise an answer always exists.Hint 2
Since a subsequence may take elements in any positions, only the count of each power matters. Go through the bits of
targetfrom the lowest.Hint 3
Small pieces can combine: two leftover
2^bact as one2^(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
- If
sum(nums) < target, return-1(use 64-bit for the sum). - Count
cnt[b], the number of elements equal to2^b. - For
bfrom 0 to 30: if bitboftargetis set, use one2^bifcnt[b] > 0; otherwise find the smallestj > bwithcnt[j] > 0, addj - bto the answer, decrementcnt[j], and add one to eachcnt[b] .. cnt[j - 1](splitting leaves one spare at each level, and the second2^bis the one used). - Then carry:
cnt[b + 1] += cnt[b] / 2, since two unused2^bsum to2^(b+1). - 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
numscan 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 opsJava
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