# Minimum Operations to Form Subsequence With Target Sum
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-operations-to-form-subsequence-with-target-sum)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-form-subsequence-with-target-sum
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Media.net](https://scaleengineer.com/companies/media.net)
---
## 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.

**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`

# Approaches
## Brute-Force Simulation with BFS
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/2`s, 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.
**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.
**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.
### Explanation
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.
### Algorithm
1. 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.
2. Use a Breadth-First Search (BFS) to explore the state space, starting from the initial state derived from the input `nums` array.
3. 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.
4. The BFS proceeds in levels, where each level corresponds to one operation. Initialize `operations = 0`.
5. 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.
6. After processing all states at the current level, increment `operations`.
7. If the queue becomes empty and no solution has been found, it's impossible to form the target sum.

## Greedy Bit-by-Bit Approach
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.
**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.
**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.
### Explanation
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^i`s 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.

```java
class Solution {
    public int minOperations(int[] nums, int target) {
        long sum = 0;
        for (int n : nums) {
            sum += n;
        }
        if (sum < target) {
            return -1;
        }

        int[] counts = new int[45];
        for (int num : nums) {
            counts[Integer.numberOfTrailingZeros(num)]++;
        }

        int operations = 0;
        for (int i = 0; i < 44; i++) {
            // Step 1: Satisfy the target's need for the i-th bit
            if (i < 32 && ((target >> i) & 1) == 1) {
                if (counts[i] > 0) {
                    counts[i]--;
                } else {
                    // Find the smallest available power of 2 greater than i
                    int j = i + 1;
                    while (j < 45 && counts[j] == 0) {
                        j++;
                    }
                    // This check is for safety; due to the initial sum check, j should be found.
                    if (j == 45) return -1; 

                    operations += (j - i);
                    counts[j]--; // Use this power of 2
                    // It gets broken down, adding one to each power from j-1 down to i
                    for (int k = j - 1; k >= i; k--) {
                        counts[k]++;
                    }
                }
            }
            
            // Step 2: Carry over excess powers to the next level
            if (i + 1 < 45) {
                counts[i+1] += counts[i] / 2;
            }
        }
        
        return operations;
    }
}
```
### Algorithm
1. 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.
2. 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).
3. Initialize `operations = 0`.
4. Iterate from `i = 0` up to a safe upper limit (e.g., 44). This loop processes powers of two from smallest to largest.
5. 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]`.
6. After the loop finishes, return the total `operations`.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(List<Integer> nums, int target) {
    long s = 0;
    int[] cnt = new int[32];
    for (int x : nums) {
      s += x;
      for (int i = 0; i < 32; ++i) {
        if ((x >> i & 1) == 1) {
          ++cnt[i];
        }
      }
    }
    if (s < target) {
      return -1;
    }
    int i = 0, j = 0;
    int ans = 0;
    while (true) {
      while (i < 32 && (target >> i & 1) == 0) {
        ++i;
      }
      if (i == 32) {
        return ans;
      }
      while (j < i) {
        cnt[j + 1] += cnt[j] / 2;
        cnt[j] %= 2;
        ++j;
      }
      while (cnt[j] == 0) {
        cnt[j] = 1;
        ++j;
      }
      ans += j - i;
      --cnt[j];
      j = i;
      ++i;
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums, int target) {
    long long s = 0;
    int cnt[32]{};
    for (int x : nums) {
      s += x;
      for (int i = 0; i < 32; ++i) {
        if (x >> i & 1) {
          ++cnt[i];
        }
      }
    }
    if (s < target) {
      return -1;
    }
    int i = 0, j = 0;
    int ans = 0;
    while (1) {
      while (i < 32 && (target >> i & 1) == 0) {
        ++i;
      }
      if (i == 32) {
        return ans;
      }
      while (j < i) {
        cnt[j + 1] += cnt[j] / 2;
        cnt[j] %= 2;
        ++j;
      }
      while (cnt[j] == 0) {
        cnt[j] = 1;
        ++j;
      }
      ans += j - i;
      --cnt[j];
      j = i;
      ++i;
    }
  }
};

```

### Python

```python
class Solution:
    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

```