Minimum Operations to Form Subsequence With Target Sum

Hard

#2535Time: O(S * C), where S is the number of states and C is the complexity of checking for a valid subsequence in each state. This is prohibitively slow and will time out.Space: O(S), where S is the number of reachable states. The state space can be enormous, so this is practically unbounded for the given constraints.1 company

Patterns

Greedy Bit Manipulation

Data structures

Array

Companies

Media.net

Prompt

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] <= 2³⁰
nums consists only of non-negative powers of two.
1 <= target < 2³¹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach treats the problem as a search for the shortest path in a graph of states. Each state represents a possible configuration of the nums array, defined by the counts of each power of two it contains. The initial state is the configuration of the input nums array. An operation, which splits a number x into two x/2s, represents a transition from one state to another.

We can use Breadth-First Search (BFS) to find the minimum number of operations. BFS explores the state graph level by level, where each level corresponds to an increasing number of operations. We start with the initial state and, at each step, generate all possible next states by applying one operation. We check each new state to see if a subsequence summing to the target can be formed. The first time we find such a state, the number of levels we have traversed gives us the minimum number of operations.

Algorithm

Model the problem as a shortest path search on a state graph. A state is defined by the frequency map of the powers of two available in the nums array.
Use a Breadth-First Search (BFS) to explore the state space, starting from the initial state derived from the input nums array.
Maintain a queue for the BFS and a visited set to store frequency maps of states that have already been processed to avoid redundant computations.
The BFS proceeds in levels, where each level corresponds to one operation. Initialize operations = 0.
In each level of the BFS: a. Dequeue all states for the current level. b. For each state (represented by a frequency map counts), check if a subsequence summing to target can be formed. This sub-problem can be solved by a greedy check on the powers of two. c. If a valid subsequence can be formed, return the current operations count as it's the minimum. d. If not, generate all possible next states by applying one operation. For each number 2^p > 1 present in the current state, create a new state by decrementing the count of 2^p and incrementing the count of 2^(p-1) by two. e. Add any new, unvisited states to the queue for the next level.
After processing all states at the current level, increment operations.
If the queue becomes empty and no solution has been found, it's impossible to form the target sum.

Walkthrough

The algorithm begins by creating a frequency map of the powers of two in the initial nums array. This map represents the starting state. A queue is initialized with this state, and a set is used to keep track of visited states to prevent cycles and redundant work.

The BFS proceeds in levels. At each level, we process all the states currently in the queue. For each state, we first perform a check to see if the numbers it represents can form a subsequence that sums to the target. If they can, we have found the shortest path, and the current level number is our answer.

If not, we generate all valid successor states. A successor is created by choosing any power of two, 2^p (where p > 0), that exists in the current state's frequency map, and applying the operation: decrease the count of 2^p by one and increase the count of 2^(p-1) by two. Each newly generated state that has not been visited before is added to the queue for the next level and marked as visited.

This process continues until a solution is found or the queue becomes empty. While correct in theory, the number of possible states can grow very large, making this approach impractical for the given problem constraints.

Complexity

Time

O(S * C), where S is the number of states and C is the complexity of checking for a valid subsequence in each state. This is prohibitively slow and will time out.

Space

O(S), where S is the number of reachable states. The state space can be enormous, so this is practically unbounded for the given constraints.

Trade-offs

Pros

Guaranteed to find the minimum number of operations if a solution exists.
Provides a clear and fundamental way to model the problem.

Cons

Extremely high time complexity, making it infeasible for the given constraints.
Very high space complexity due to the need to store a large number of states in the queue and visited set.
The state representation (a frequency map) and the subsequence sum check within each step add implementation complexity.

A highly efficient greedy approach can solve this problem by considering the binary representation of the target sum. The core idea is to satisfy the required powers of two for the target one by one, starting from the smallest power (2^0).

We maintain a frequency count of the powers of two we currently possess, initialized from the nums array. We iterate through the bits of the target from least significant to most significant. If the current bit i is set in target, we need a 2^i. We first check if we have one available. If so, we use it. If not, we must create one by breaking down a larger power of two. To minimize operations, we greedily choose the smallest available power 2^j (with j > i) and perform j - i operations to obtain a 2^i. Any excess powers of two at each step are 'carried over' by combining them into the next higher power.

Algorithm

First, calculate the total sum of elements in nums. If this sum is less than target, it's impossible to form the subsequence, so return -1.
Create a frequency array counts to store the counts of each power of two in nums. For each num in nums, which is 2^p, increment counts[p]. The size of this array should be large enough to handle carry-overs (e.g., size 45).
Initialize operations = 0.
Iterate from i = 0 up to a safe upper limit (e.g., 44). This loop processes powers of two from smallest to largest.
In each iteration i: a. Check if the i-th bit of target is set. If (target >> i) & 1 == 1, we need a 2^i. b. If we need a 2^i: i. If counts[i] > 0, we have one available. Use it by decrementing counts[i]. ii. If counts[i] == 0, we must create a 2^i by breaking down a larger power. Find the smallest j > i for which counts[j] > 0. iii. Add j - i to operations. This is the number of splits required to turn a 2^j into a 2^i. iv. Decrement counts[j] as it's been used. For each power k from j-1 down to i, increment counts[k] because breaking 2^j creates these intermediate powers. c. After satisfying the target's need for 2^i, combine any remaining pairs of 2^i to form 2^(i+1). Add counts[i] / 2 to counts[i+1].
After the loop finishes, return the total operations.

Walkthrough

This method is based on a greedy strategy that processes the required powers of two from smallest to largest.

First, as a necessary condition, if the sum of all numbers in nums is less than target, no amount of operations can create the required sum, so we return -1.

Next, we populate a frequency array, counts, where counts[p] stores the number of 2^p's we have. We can use Integer.numberOfTrailingZeros(num) to efficiently find p for each num.

The main logic iterates from i = 0 upwards. For each i, we check if target requires a 2^i (i.e., if the i-th bit of target is 1). If it does, we check counts[i]. If counts[i] is positive, we use one 2^i and decrement the count. If counts[i] is zero, we are forced to create a 2^i. The most efficient way to do this is to find the smallest available power 2^j with j > i, and break it down. This takes j - i operations. We add this to our total operations count, decrement counts[j], and increment counts[k] for all k from i to j-1 to account for the new powers created in the process.

After satisfying the potential need for 2^i, any remaining 2^is in counts[i] are paired up and carried over to the next level: counts[i+1] += counts[i] / 2. This ensures that we efficiently use all available numbers.

This process is repeated for all bits of the target and for any remaining carried-over numbers. The final accumulated number of operations is the minimum required.

1class Solution {2    public int minOperations(int[] nums, int target) {3        long sum = 0;4        for (int n : nums) {5            sum += n;6        }7        if (sum < target) {8            return -1;9        }10 11        int[] counts = new int[45];12        for (int num : nums) {13            counts[Integer.numberOfTrailingZeros(num)]++;14        }15 16        int operations = 0;17        for (int i = 0; i < 44; i++) {18            // Step 1: Satisfy the target's need for the i-th bit19            if (i < 32 && ((target >> i) & 1) == 1) {20                if (counts[i] > 0) {21                    counts[i]--;22                } else {23                    // Find the smallest available power of 2 greater than i24                    int j = i + 1;25                    while (j < 45 && counts[j] == 0) {26                        j++;27                    }28                    // This check is for safety; due to the initial sum check, j should be found.29                    if (j == 45) return -1; 30 31                    operations += (j - i);32                    counts[j]--; // Use this power of 233                    // It gets broken down, adding one to each power from j-1 down to i34                    for (int k = j - 1; k >= i; k--) {35                        counts[k]++;36                    }37                }38            }39            40            // Step 2: Carry over excess powers to the next level41            if (i + 1 < 45) {42                counts[i+1] += counts[i] / 2;43            }44        }45        46        return operations;47    }48}

Complexity

Time

O(N + C), where N is the length of `nums` and C is a constant representing the number of bits to process (e.g., 45). This simplifies to O(N) as C is constant.

Space

O(1), as the `counts` array has a fixed size independent of the input `nums` array's length.

Trade-offs

Pros

Highly efficient with linear time complexity relative to the input size.
Low and constant space complexity.
Correctly finds the minimum number of operations by making locally optimal choices.

Cons

The logic requires careful handling of indices and bit manipulation, which can be slightly error-prone.
Requires understanding of binary representations and properties of powers of two.

Solutions

Solution

1class Solution {2public3  int minOperations(List<Integer> nums, int target) {4    long s = 0;5    int[] cnt = new int[32];6    for (int x : nums) {7      s += x;8      for (int i = 0; i < 32; ++i) {9        if ((x >> i & 1) == 1) {10          ++cnt[i];11        }12      }13    }14    if (s < target) {15      return -1;16    }17    int i = 0, j = 0;18    int ans = 0;19    while (true) {20      while (i < 32 && (target >> i & 1) == 0) {21        ++i;22      }23      if (i == 32) {24        return ans;25      }26      while (j < i) {27        cnt[j + 1] += cnt[j] / 2;28        cnt[j] %= 2;29        ++j;30      }31      while (cnt[j] == 0) {32        cnt[j] = 1;33        ++j;34      }35      ans += j - i;36      --cnt[j];37      j = i;38      ++i;39    }40  }41}

1class Solution {2public:3  int minOperations(vector<int> &nums, int target) {4    long long s = 0;5    int cnt[32]{};6    for (int x : nums) {7      s += x;8      for (int i = 0; i < 32; ++i) {9        if (x >> i & 1) {10          ++cnt[i];11        }12      }13    }14    if (s < target) {15      return -1;16    }17    int i = 0, j = 0;18    int ans = 0;19    while (1) {20      while (i < 32 && (target >> i & 1) == 0) {21        ++i;22      }23      if (i == 32) {24        return ans;25      }26      while (j < i) {27        cnt[j + 1] += cnt[j] / 2;28        cnt[j] %= 2;29        ++j;30      }31      while (cnt[j] == 0) {32        cnt[j] = 1;33        ++j;34      }35      ans += j - i;36      --cnt[j];37      j = i;38      ++i;39    }40  }41};

1class Solution:2    def minOperations(self, nums: List[int], target: int) -> int: s = sum(nums) if s < target: return - 1 cnt = [0] * 32 for x in nums: for i in range(32): if x >> i & 1: cnt[i] += 1 i = j = 0 ans = 0 while 1: while i < 32 and (target >> i & 1) == 0: i += 1 if i == 32: break while j < i: cnt[j + 1] += cnt[j] // 2 cnt[j] %= 2 j += 1 while cnt[j] == 0: cnt[j] = 1 j += 1 ans += j - i cnt[j] -= 1 j = i i += 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem