# Construct Target Array With Multiple Sums
**Difficulty:** HARD
[External](https://leetcode.com/problems/construct-target-array-with-multiple-sums)
Canonical: https://scaleengineer.com/dsa/problems/construct-target-array-with-multiple-sums
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Quora](https://scaleengineer.com/companies/quora)
---
## Problem
You are given an array `target` of n integers. From a starting array `arr` consisting of `n` 1's, you may perform the following procedure :

* let `x` be the sum of all elements currently in your array.
* choose index `i`, such that `0 <= i < n` and set the value of `arr` at index `i` to `x`.
* You may repeat this procedure as many times as needed.

Return `true` _if it is possible to construct the_ `target` _array from_ `arr`_, otherwise, return_ `false`.

**Example 1:**

**Input:** target = [9,3,5]
**Output:** true
**Explanation:** Start with arr = [1, 1, 1] 
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done

**Example 2:**

**Input:** target = [1,1,1,2]
**Output:** false
**Explanation:** Impossible to create target array from [1,1,1,1].

**Example 3:**

**Input:** target = [8,5]
**Output:** true

**Constraints:**

* `n == target.length`
* `1 <= n <= 5 * 104`
* `1 <= target[i] <= 109`

# Approaches
## Brute-Force Backward Simulation
This approach simulates the process in reverse, starting from the `target` array and trying to reach the initial `[1, 1, ..., 1]` array. The logic is that the largest element in the current array must have been the one generated in the last step. We can undo this step by subtracting the sum of the other elements from this largest element. We repeat this process until all elements become 1. To find the largest element at each step, we perform a linear scan of the array.
**Time:** O(K * N), where N is the length of the array and K is the number of backward steps. K can be very large, proportional to the maximum value in `target`, making this solution too slow. · **Space:** O(1) if the input array is modified in-place. O(N) if a copy of the array is used.
**Pros:** Simple to understand and reason about.; Low space complexity as it can modify the array in-place.
**Cons:** Extremely inefficient for large input values as the numbers decrease by a small amount in each step.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
### Explanation
This method is a direct implementation of the backward simulation logic. While it's conceptually simple, its performance is poor due to the repeated linear scans and the potentially large number of steps required to reduce the target values to 1.

For example, if `target = [1, 10^9]`, the process would be:
`[1, 10^9]` -> `[1, 10^9 - 1]` -> `[1, 10^9 - 2]` ...
This would require nearly `10^9` steps, each involving a scan of the array, making it infeasible.

```java
class Solution {
    public boolean isPossible(int[] target) {
        if (target.length == 1) {
            return target[0] == 1;
        }

        long sum = 0;
        for (int val : target) {
            sum += val;
        }

        while (true) {
            int maxIdx = -1;
            int maxVal = -1;
            for (int i = 0; i < target.length; i++) {
                if (target[i] > maxVal) {
                    maxVal = target[i];
                    maxIdx = i;
                }
            }

            if (maxVal == 1) {
                return true; // All elements are 1
            }

            long restSum = sum - maxVal;

            if (restSum == 0 || maxVal <= restSum) {
                return false;
            }

            int prevVal = (int) (maxVal - restSum);
            if (prevVal < 1) {
                return false;
            }

            sum = sum - maxVal + prevVal;
            target[maxIdx] = prevVal;
        }
    }
}
```
### Algorithm
The core idea is to work backward from the `target` array to the initial array of all ones. The forward process involves replacing an element `arr[i]` with the sum of all elements. This implies that at any step, the largest element in the array must have been the one that was just created. We can reverse this process:

1.  Start a loop that continues as long as the largest element in the array is greater than 1.
2.  In each iteration, find the largest element `maxVal` and its index `maxIdx` by scanning the array.
3.  Calculate the sum of all other elements, `restSum`.
4.  The value of the element at `maxIdx` before this step must have been `prevVal = maxVal - restSum`.
5.  Check for invalid states:
    *   If `maxVal <= restSum`, then `prevVal` would be less than or equal to 0. Since we start with all 1s and only add positive numbers, all elements must always be positive. This is an impossible state, so we return `false`.
    *   If `restSum` is 0 (and `n > 1`), it's also impossible as all elements must be at least 1.
6.  Update the array by setting the element at `maxIdx` to `prevVal`.
7.  If the loop completes, it means the largest element is 1, which implies all elements are 1. We have successfully reached the starting state, so we return `true`.

## Optimized Backward Simulation with Max-Heap
This approach significantly improves the backward simulation by using a max-heap to efficiently find the largest element and employing modulo arithmetic to bypass a large number of redundant subtraction steps. By replacing `maxVal` with `maxVal % restSum`, we can reduce large numbers to a value smaller than the second-largest element in just one operation, drastically cutting down the number of iterations needed.
**Time:** O(N + log(M) * log(N)), where N is the array size and M is the maximum element in `target`. O(N) is for building the heap. The number of loop iterations is logarithmic with respect to M due to the modulo operation, and each iteration costs O(log N) for heap operations. · **Space:** O(N), where N is the length of the `target` array, for storing the elements in the priority queue.
**Pros:** Highly efficient and passes within the time limits for large inputs.; Correctly handles edge cases and large numbers using modulo arithmetic.
**Cons:** Requires more complex data structures (a heap).; Uses more space to store the elements in the heap.
### Explanation
The use of a max-heap reduces the time to find the maximum element from O(N) to O(log N). The modulo arithmetic is the key optimization for performance. If we have a state like `[100, 3]`, the sum is 103, `maxVal` is 100, and `restSum` is 3. Instead of doing `100-3=97`, `97-3=94`, etc., we can directly compute the new value as `100 % 3 = 1`. This transforms the array to `[1, 3]` in a single step, which is much faster.

```java
import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public boolean isPossible(int[] target) {
        // Handle edge case for n=1
        if (target.length == 1) {
            return target[0] == 1;
        }

        // Use a max-heap to easily access the largest element
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        long sum = 0;
        for (int num : target) {
            sum += num;
            maxHeap.add(num);
        }

        // Work backwards from the target
        while (maxHeap.peek() > 1) {
            int maxVal = maxHeap.poll();
            long restSum = sum - maxVal;

            // If restSum is 1, we can always form the target.
            // The other n-1 elements are 1s, and we can reduce maxVal to 1
            // by repeatedly subtracting 1 (the restSum).
            if (restSum == 1) {
                return true;
            }

            // If maxVal is smaller than or equal to the rest, we can't go back.
            // prevVal = maxVal - restSum would be <= 0.
            // restSum can't be 0 if n > 1 and all elements are positive.
            if (maxVal <= restSum || restSum == 0) {
                return false;
            }

            // Use modulo to perform multiple subtractions at once
            int prevVal = (int) (maxVal % restSum);

            // If maxVal is a multiple of restSum, prevVal becomes 0, which is invalid.
            // This is only possible if the previous element was also a multiple of restSum,
            // which can't be true starting from 1s.
            if (prevVal == 0) {
                return false;
            }

            // Update sum and add the new element to the heap
            sum = restSum + prevVal;
            maxHeap.add(prevVal);
        }

        // If we reach here, all elements are 1s
        return true;
    }
}
```
### Algorithm
This optimized approach also works backward but addresses the two main inefficiencies of the brute-force method.

1.  **Finding the Maximum:** Instead of a linear scan, a max-heap (implemented as a `PriorityQueue` in Java) is used. This allows us to retrieve the maximum element in O(log N) time.
2.  **Reducing Large Numbers:** When the largest element `maxVal` is significantly larger than the sum of the rest `restSum`, repeatedly subtracting `restSum` is slow. This series of subtractions is equivalent to the modulo operation. The new value can be calculated in one step as `prevVal = maxVal % restSum`.

**The Algorithm:**
1.  Handle edge cases: If `n=1`, return `true` only if `target[0] == 1`.
2.  Calculate the total sum of elements (using a `long` to avoid overflow) and push all elements into a max-heap.
3.  Loop as long as the top element of the heap is greater than 1.
4.  In each iteration:
    a. Pop the largest element `maxVal` from the heap.
    b. Calculate `restSum = sum - maxVal`.
    c. Check for failure/termination conditions:
        i. If `restSum == 1`, it means all other elements are 1s. We can always reduce `maxVal` to 1 by subtracting 1 repeatedly. So, we can return `true`.
        ii. If `maxVal <= restSum` or `restSum == 0`, the state is invalid. Return `false`.
    d. Calculate the previous value using the modulo optimization: `prevVal = maxVal % restSum`.
    e. If `prevVal` is 0 (which happens if `maxVal` is a multiple of `restSum`), it's an impossible state because `restSum > 1` at this point. Return `false`.
    f. Insert `prevVal` back into the heap.
    g. Update the total sum: `sum = restSum + prevVal`.
5.  If the loop completes, all elements are 1. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean isPossible(int[] target) {
    PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
    long s = 0;
    for (int x : target) {
      s += x;
      pq.offer((long)x);
    }
    while (pq.peek() > 1) {
      long mx = pq.poll();
      long t = s - mx;
      if (t == 0 || mx - t < 1) {
        return false;
      }
      long x = mx % t;
      if (x == 0) {
        x = t;
      }
      pq.offer(x);
      s = s - mx + x;
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isPossible(vector<int> &target) {
    priority_queue<int> pq;
    long long s = 0;
    for (int i = 0; i < target.size(); i++) {
      s += target[i];
      pq.push(target[i]);
    }
    while (pq.top() != 1) {
      int mx = pq.top();
      pq.pop();
      long long t = s - mx;
      if (t < 1 || mx - t < 1) {
        return false;
      }
      int x = mx % t;
      if (x == 0) {
        x = t;
      }
      pq.push(x);
      s = s - mx + x;
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def isPossible(self, target: List[int]) -> bool: s = sum(target) pq = [- x for x in target] heapify(pq) while - pq[0] > 1: mx = - heappop(pq) t = s - mx if t == 0 or mx - t < 1: return False x = (mx % t) or t heappush(pq, - x) s = s - mx + x return True

```