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.
This approach relies on greedily breaking down larger elements in nums as needed to attempt to reach the target sum. The main idea is to utilize larger numbers as potential resources to break down only when needed to fulfill the binary representation requirements of the target sum.
The C solution sorts the nums array, and then iterates backward, subtracting the largest available number from the target and breaking it into smaller pieces if necessary (counting each break as one operation). The process stops when we've achieved zero remainder in the target or run out of numbers to use.
Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) because we are modifying the array in place.
This approach involves using a dynamic programming technique to explore the state space efficiently. The idea is to represent states as the current sum and the position in the array, and systematically discover valid subsequence sums while counting operations.
This solution uses a dynamic programming table dp where dp[j] holds the minimum operations needed to achieve a sum of j. It iterates over the powers of 2 and simulates adding them into the subsequence, thereby updating the state space in a bottom-up manner.
Time Complexity: O(n * target), Space Complexity: O(target).
Observing the operation in the problem, we find that each operation actually splits a number greater than 1 into two equal numbers, which means that the sum of the elements in the array will not change after the operation. Therefore, if the sum of the elements in the array s is less than target, it is impossible to obtain a subsequence with a sum of target through the operation described in the problem, and we can directly return -1. Otherwise, we can definitely make the sum of some subsequences in the array equal to target through the split operation.
In addition, the split operation will actually set the binary high bit of the number to 0 and add 2 to the lower bit. Therefore, we first use an array of length 32 to record the number of times 1 appears on each binary bit in the binary representation of all elements in the array nums.
Next, starting from the low bit of target, for the ith bit of target, if the current bit number is 0, skip it directly, that is, i = i + 1. If the current bit number is 1, we need to find the smallest number j (where j \ge i) in the array cnt such that cnt[j] > 0, and then we split the number 1 at this bit to the lower bit i, that is, subtract 1 from cnt[j], and set each bit from i to j-1 in cnt to 1, and the number of operations is j-i. Next, we let j = i, and then i = i + 1. Repeat the above operation until i exceeds the index range of the array cnt, and return the number of operations at this time.
Note that if j < i, actually two lower bits of 1 can be combined into a higher bit of 1. Therefore, if j < i, we add \frac{cnt[j]}{2} to cnt[j+1], and take cnt[j] modulo 2, then let j = j + 1, and continue the above operation.
The time complexity is O(n times log M), and the space complexity is O(log M). Here, n is the length of the array nums, and M is the maximum value in the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Approach to Break Larger Elements | Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) because we are modifying the array in place. |
| Approach 2: Dynamic Programming with State Space Exploration | Time Complexity: O(n * target), Space Complexity: O(target). |
| Greedy + Bit Manipulation | — |
| 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 |
Leetcode Weekly contest 360 - Hard - Minimum Operations to Form Subsequence With Target Sum • Prakhar Agrawal • 3,334 views views
Watch 9 more video solutions →Practice Minimum Operations to Form Subsequence With Target Sum with our built-in code editor and test cases.
Practice on FleetCode