Watch 10 video solutions for Minimum Operations to Form Subsequence With Target Sum, a hard level problem involving Array, Greedy, Bit Manipulation. This walkthrough by Prakhar Agrawal has 3,334 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
nums[i] such that nums[i] > 1.nums[i] from the array.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 <= 10001 <= nums[i] <= 230nums consists only of non-negative powers of two.1 <= target < 231Problem Overview: You are given an array where every number is a power of two. You may split any number into two equal halves (one operation). The goal is to form a subsequence whose sum equals target using the minimum number of split operations.
Approach 1: Greedy Approach to Break Larger Elements (O(n + log target) time, O(log target) space)
This approach relies on bit manipulation. Since every number is a power of two, represent both the array and the target using bit counts. Count how many numbers exist for each bit position. Then iterate from the least significant bit to the most significant bit of the target. If the current bit requires a value but none exists, search for a higher bit and repeatedly split it (each split doubles the count of the next lower bit). Each split counts as one operation. Surplus bits can be carried upward because two 2^k values combine into 2^(k+1). This greedy strategy always uses the smallest available pieces first and only breaks larger numbers when necessary.
Approach 2: Dynamic Programming with State Space Exploration (O(n * target) time, O(target) space)
A more general solution models the problem as a subset-sum style DP using the array values. For each number, you explore states representing achievable sums while also considering the cost of splitting larger powers into smaller ones. Each split produces two smaller elements that can contribute to future states. While this works conceptually similar to knapsack DP, the state space grows quickly because the target can be large and splitting introduces many intermediate values. This method demonstrates correctness but is rarely practical for the largest constraints.
Recommended for interviews: The greedy bit-count solution is what interviewers expect. It combines greedy reasoning with bit frequency tracking from the array. Showing the DP formulation first can demonstrate understanding of the problem structure, but the greedy approach proves you can recognize power-of-two structure and optimize using bit operations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Bit Counting with Splitting | O(n + log target) | O(log target) | Best for large inputs where numbers are powers of two and you want the optimal interview solution |
| Dynamic Programming State Exploration | O(n * target) | O(target) | Useful for understanding subset-sum style reasoning or when constraints are small |