Skip to main content
Talentd

Minimum Operations to Form Subsequence With Target Sum - Solution & Explanation

HardArrayGreedyBit Manipulation24 min readAsked at: Medianet
Practice this problem

Problem Statement

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.

 

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 <= 1000
  • 1 <= nums[i] <= 230
  • nums consists only of non-negative powers of two.
  • 1 <= target < 231

Approach Overview

Problem 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 1: Approach 1: Greedy Approach to Break Larger Elements

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) because we are modifying the array in place.

Try this approach in the editor →

Approach 2: Approach 2: Dynamic Programming with State Space Exploration

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * target), Space Complexity: O(target).

Try this approach in the editor →

Approach 3: Greedy + Bit Manipulation

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Bit Counting with SplittingO(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 ExplorationO(n * target)O(target)Useful for understanding subset-sum style reasoning or when constraints are small

Video Solution

Leetcode Weekly contest 360 - Hard - Minimum Operations to Form Subsequence With Target Sum • Prakhar Agrawal • 3,341 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Form Subsequence With Target Sum easy or hard?
The problem is labeled Hard because the key insight is recognizing the power-of-two structure and applying greedy bit manipulation. Without that observation, many candidates attempt expensive subset-sum or DP solutions that do not scale to large inputs.
Minimum Operations to Form Subsequence With Target Sum Python/Java solution
Most implementations maintain a frequency array of bit counts (typically up to 31 or 32 bits). The algorithm iterates through target bits, uses available counts, and splits larger bits when required. The same logic translates directly to Python, Java, C++, and JavaScript because it relies on simple loops and bit shifts.
How to solve Minimum Operations to Form Subsequence With Target Sum in O(n)?
An almost linear solution uses greedy bit counting. First count how many numbers correspond to each power of two. Traverse the bits of the target and use available counts; if a bit is missing, split a higher power into smaller pieces until the required bit appears. The work across all bit levels stays proportional to n plus the number of bits in the target.
What is the best approach for Minimum Operations to Form Subsequence With Target Sum?
The optimal approach uses a greedy strategy with bit manipulation. Count how many powers of two exist at each bit position, then iterate through the target bits from low to high. When a required bit is missing, split the nearest larger power of two until the needed value appears. This runs in about O(n + log target) time and uses O(log target) space.
Is Minimum Operations to Form Subsequence With Target Sum asked at Google/Amazon/Meta?
Problems combining greedy logic with bit manipulation frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of power-of-two splitting or bit-frequency reasoning are common in system-level algorithm interviews.
What data structure is used in Minimum Operations to Form Subsequence With Target Sum?
The main structure is an array or frequency table storing counts of each power-of-two bit. Bit manipulation operations determine which bits are needed for the target and where splits must occur.
What is the time complexity of Minimum Operations to Form Subsequence With Target Sum?
The optimal greedy solution runs in O(n + log target) time because it first counts bit frequencies from the array and then processes each bit position of the target. Splitting operations only traverse a limited number of bit levels. Space complexity is O(log target) for storing counts of powers of two.

Ready to solve this problem?

Practice Minimum Operations to Form Subsequence With Target Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Closest Subsequence Sum

Next

Number of Subsequences That Satisfy the Given Sum Condition