Minimum Operations to Form Subsequence With Target Sum

Minimum Operations to Form Subsequence With Target Sum - 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 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.

Input & Output

Example 1 — Basic Split Required

$ Input: nums = [1,1,4], target = 3

› Output: 1

💡 Note: We have two 1s and one 4. To form target 3, we need a 2. We can split 4 → [2,2] in 1 operation, then use 1+2=3.

Example 2 — No Operations Needed

$ Input: nums = [1,2,8], target = 3

› Output: 0

💡 Note: We already have 1 and 2 in the array. We can directly form 1+2=3 without any operations.

Example 3 — Impossible Case

$ Input: nums = [1,2], target = 4

› Output: -1

💡 Note: Total sum is 1+2=3, which is less than target 4. It's impossible to reach target 4.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 10⁶
nums[i] is a power of 2
1 ≤ target ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array of powers of 2 and target sum to achieve

Split Strategy

Split larger denominations into smaller ones when needed

Form Target

Use greedy approach to select subsequence summing to target

Key Takeaway

🎯 Key Insight: Use greedy bit manipulation to process target bit-by-bit and minimize splits

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to use greedy bit manipulation - process target bit by bit and split larger powers of 2 only when needed. The optimal approach counts frequencies and uses binary representation to minimize operations. Time: O(log target), Space: O(log max(nums)).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Bit Manipulation	O(log target)	O(log max(nums))	Use greedy approach to minimize splits by working with bit representation
Brute Force Simulation	O(2^n)	O(2^n)	Try all possible combinations of operations and check if target can be formed

Greedy Bit Manipulation — Algorithm Steps

Count frequency of each power of 2 in nums
Try to form target greedily from largest to smallest powers
Split larger powers when smaller powers are insufficient

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Powers

Count frequency of each power of 2 in the array

Process Bits

For each bit in target, use available denomination or split larger ones

Count Operations

Each split contributes to the operation count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_POWER 21

int solution(int* nums, int numsSize, int target) {
    int count[1 << MAX_POWER] = {0};
    long long totalSum = 0;
    
    for (int i = 0; i < numsSize; i++) {
        count[nums[i]]++;
        totalSum += nums[i];
    }
    
    if (totalSum < target) {
        return -1;
    }
    
    int operations = 0;
    
    for (int i = 0; i < MAX_POWER; i++) {
        int powerOf2 = 1 << i;
        
        if (target & powerOf2) {
            if (count[powerOf2] > 0) {
                count[powerOf2]--;
            } else {
                int found = 0;
                for (int j = i + 1; j < MAX_POWER; j++) {
                    int largerPower = 1 << j;
                    if (count[largerPower] > 0) {
                        count[largerPower]--;
                        
                        for (int k = i; k < j; k++) {
                            int smallerPower = 1 << k;
                            int addCount = 1 << (j - k - 1);
                            count[smallerPower] += addCount;
                        }
                        
                        count[powerOf2]--;
                        operations += j - i;
                        found = 1;
                        break;
                    }
                }
                
                if (!found) {
                    return -1;
                }
            }
        }
    }
    
    return operations;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* ptr = strchr(line, '[');
    ptr++;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int target;
    scanf("%d", &target);
    
    printf("%d\n", solution(nums, numsSize, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log target)

We iterate through at most log(target) bit positions

⚡ Linearithmic

Space Complexity

O(log max(nums))

Counter stores at most log(max element) different powers of 2

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

428 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Bit Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler