# 1354 Construct Target Array With Multiple Sums

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
[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`
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 `````` ``````import heapq class Solution: def isPossible(self, target: List[int]) -> bool: if len(target) == 1: return target ==  total = sum(target) heap = [-num for num in target] heapq.heapify(heap) while -heap > 1: largest = -heap rest = total - largest if rest == 1: # only possible when n=2 return True # since the largest was updated every time # this is fater than deducting by rest repeatedly x = largest % rest if x == 0 or x == largest: return False # same as pop and push new min, but faster heapq.heapreplace(heap, -x) total = total - largest + x return True``````