Minimum Operations to Form Subsequence With Target Sum solution and explanation
9 more videos on this problem
Leetcode Weekly contest 360 - Hard - Minimum Operations to Form Subsequence With Target SumPrakhar Agrawal · 25:51 · 3K views
2835. Minimum Operations to Form Subsequence With Target Sum | Weekly Leetcode 360codingMohan · 35:37 · 2K views
2835. Minimum Operations to Form Subsequence With Target Sum || Weekly Contest 360 || LeetcodeAshish Kumar · 20:38 · 1K views
minimum operations to form subsequence with target sum #leetcode #leetcodechallengecrazy developers · 0:26 · 1K views
【每日一题】LeetCode 2835. Minimum Operations to Form Subsequence With Target SumHuifeng Guan · 22:07 · 717 views
2835. Minimum Operations to Form Subsequence With Target Sum | Weekly Leetcode 360codingMohan · 27:38 · 608 views
2835. Minimum Operations to Form Subsequence With Target Sum (Leetcode Hard)Programming Live with Larry · 54:33 · 460 views
Leetcode 2835|| Minimum Operations to Form Subsequence With Target Sum ||Leetcode Weekly Hard || cppKomal Pal · 18:02 · 259 views
LeetCode 2835. Minimum Operations to Form Subsequence With Target Sum || Weekly contest 360 || hardRandom Chronicles · 17:50 · 154 views
2835. Minimum Operations to Form Subsequence With Target SumDhananjoy Dey · 16:54 · 138 views
The problem
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 thatnums[i] > 1. - Remove
nums[i]from the array. - Add two occurrences of
nums[i] / 2to the end ofnums.
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] <= 230numsconsists 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.
def min_operations(nums, target):
nums.sort(reverse=True)
ops = 0
for num in nums:
while num > 0 and target >= num:
target -= num
ops += 1
if target == 0:
return ops
return -1
nums = [1, 32, 1, 2]
target = 12
result = min_operations(nums, target)
print(f"Result: {result}")import java.util.Arrays;
public class Solution {
public static int minOperations(int[] nums, int target) {
Arrays.sort(nums);
int ops = 0;
for (int i = nums.length - 1; i >= 0; i--) {
while (nums[i] > 0 && target >= nums[i]) {
target -= nums[i];
ops++;
}
if (target == 0) return ops;
}
return -1;
}
public static void main(String[] args) {
int[] nums = {1, 32, 1, 2};
int target = 12;
System.out.println("Result: " + minOperations(nums, target));
}
}#include <vector>
#include <algorithm>
int minOperations(std::vector<int>& nums, int target) {
std::sort(nums.begin(), nums.end(), std::greater<int>());
int ops = 0;
for (int num : nums) {
while (num > 0 && target >= num) {
target -= num;
ops++;
}
if (target == 0) return ops;
}
return -1;
}
int main() {
std::vector<int> nums = {1, 32, 1, 2};
int target = 12;
int result = minOperations(nums, target);
std::cout << "Result: " << result << std::endl;
return 0;
}function minOperations(nums, target) {
nums.sort((a, b) => b - a);
let ops = 0;
for (let num of nums) {
while (num > 0 && target >= num) {
target -= num;
ops++;
}
if (target === 0) return ops;
}
return -1;
}
const nums = [1, 32, 1, 2];
const target = 12;
console.log(`Result: ${minOperations(nums, target)}`);#include <stdio.h>
#include <stdlib.h>
int minOperations(int* nums, int numsSize, int target) {
int ops = 0;
while (target > 0) {
while (numsSize > 0 && nums[numsSize - 1] > target)
numsSize--;
if (numsSize == 0)
return -1;
target -= nums[--numsSize];
ops++;
}
return ops - 1;
}
int main() {
int nums[] = {1, 32, 1, 2};
int target = 12;
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = minOperations(nums, numsSize, target);
printf("Result: %d\n", result);
return 0;
}using System;
class Solution {
public static int MinOperations(int[] nums, int target) {
Array.Sort(nums);
Array.Reverse(nums);
int ops = 0;
foreach (int num in nums) {
while (num > 0 && target >= num) {
target -= num;
ops++;
}
if (target == 0) return ops;
}
return -1;
}
static void Main() {
int[] nums = {1, 32, 1, 2};
int target = 12;
Console.WriteLine("Result: " + MinOperations(nums, target));
}
}Pythons's implementation involves sorting the nums array in descending order followed by iterative subtraction from the target until it reaches zero, while counting operations. Implements the greedy method described.
Time Complexity: O(n log n), Space Complexity: O(1).
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.
def min_operations(nums, target):
dp = [10000] * (target + 1)
dp[0] = 0
for num in nums:
for j in range(target, num - 1, -1):
dp[j] = min(dp[j], dp[j - num] + 1)
return dp[target] if dp[target] != 10000 else -1
nums = [1, 2, 8]
target = 7
result = min_operations(nums, target)
print(f"Result: {result}")import java.util.Arrays;
public class Solution {
public static int minOperations(int[] nums, int target) {
int[] dp = new int[target + 1];
Arrays.fill(dp, 10000);
dp[0] = 0;
for (int num : nums) {
for (int j = target; j >= num; --j) {
dp[j] = Math.min(dp[j], dp[j - num] + 1);
}
}
return dp[target] == 10000 ? -1 : dp[target] - 1;
}
public static void main(String[] args) {
int[] nums = {1, 2, 8};
int target = 7;
System.out.println("Result: " + minOperations(nums, target));
}
}#include <vector>
#include <algorithm>
int minOperations(std::vector<int>& nums, int target) {
std::vector<int> dp(target + 1, 10000);
dp[0] = 0;
for (int num : nums) {
for (int j = target; j >= num; --j) {
dp[j] = std::min(dp[j], dp[j - num] + 1);
}
}
return dp[target] == 10000 ? -1 : dp[target] - 1;
}
int main() {
std::vector<int> nums = {1, 2, 8};
int target = 7;
int result = minOperations(nums, target);
std::cout << "Result: " << result << std::endl;
return 0;
}function minOperations(nums, target) {
let dp = new Array(target + 1).fill(10000);
dp[0] = 0;
for (let num of nums) {
for (let j = target; j >= num; j--) {
dp[j] = Math.min(dp[j], dp[j - num] + 1);
}
}
return dp[target] === 10000 ? -1 : dp[target] - 1;
}
const nums = [1, 2, 8];
const target = 7;
console.log(`Result: ${minOperations(nums, target)}`);#include <stdio.h>
#include <string.h>
int minOperations(int* nums, int numsSize, int target) {
int dp[target + 1];
memset(dp, 10000, sizeof(dp));
dp[0] = 0;
for (int i = 0; i < numsSize; ++i) {
for (int j = target; j >= nums[i]; --j) {
dp[j] = dp[j] > dp[j - nums[i]] + 1 ? dp[j - nums[i]] + 1 : dp[j];
}
}
return dp[target] == 10000 ? -1 : dp[target] - 1;
}
int main() {
int nums[] = {1, 2, 8};
int target = 7;
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = minOperations(nums, numsSize, target);
printf("Result: %d\n", result);
return 0;
}using System;
using System.Linq;
class Solution {
public static int MinOperations(int[] nums, int target) {
int[] dp = new int[target + 1];
Array.Fill(dp, 10000);
dp[0] = 0;
foreach (int num in nums) {
for (int j = target; j >= num; --j) {
dp[j] = Math.Min(dp[j], dp[j - num] + 1);
}
}
return dp[target] == 10000 ? -1 : dp[target] - 1;
}
static void Main() {
int[] nums = {1, 2, 8};
int target = 7;
Console.WriteLine("Result: " + MinOperations(nums, target));
}
}Python code initializes the dynamic programming array dp and iterates to update each value with the operations needed. This solution employs a similar strategy to the knapsack problem by handling each number as a potential part of the subsequence.
Time Complexity: O(n * target), Space Complexity: O(target).
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.
function minOperations(nums: number[], target: number): number {
let s = 0;
const cnt: number[] = Array(32).fill(0);
for (const x of nums) {
s += x;
for (let i = 0; i < 32; ++i) {
if ((x >> i) & 1) {
++cnt[i];
}
}
}
if (s < target) {
return -1;
}
let [ans, i, j] = [0, 0, 0];
while (1) {
while (i < 32 && ((target >> i) & 1) === 0) {
++i;
}
if (i === 32) {
return ans;
}
while (j < i) {
cnt[j + 1] += cnt[j] >> 1;
cnt[j] %= 2;
++j;
}
while (cnt[j] == 0) {
cnt[j] = 1;
j++;
}
ans += j - i;
cnt[j]--;
j = i;
i++;
}
}func minOperations(nums []int, target int) (ans int) {
s := 0
cnt := [32]int{}
for _, x := range nums {
s += x
for i := 0; i < 32; i++ {
if x>>i&1 > 0 {
cnt[i]++
}
}
}
if s < target {
return -1
}
var i, j int
for {
for i < 32 && target>>i&1 == 0 {
i++
}
if i == 32 {
return
}
for j < i {
cnt[j+1] += cnt[j] >> 1
cnt[j] %= 2
j++
}
for cnt[j] == 0 {
cnt[j] = 1
j++
}
ans += j - i
cnt[j]--
j = i
i++
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Approach to Break Larger Elements | Time Complexity: O(n log n), Space Complexity: O(1). |
| Approach 2: Dynamic Programming with State Space Exploration | Time Complexity: O(n * target), Space Complexity: O(target). |
| Greedy + Bit Manipulation | – |
Complexity analysis
| 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 |
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.