Formatted question description: https://leetcode.ca/all/1354.html

# 1354. Construct Target Array With Multiple Sums (Hard)

Given an array of integers target. From a starting array, A consisting of all 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 < target.size and set the value of A 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 A 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 <= target.length <= 5 * 10^4
• 1 <= target[i] <= 10^9

Related Topics:
Greedy

## Solution 1. Work backwards

From the target, try to reach all 1s.

Case 1: [3, 5, 9]

• [3,5,9], 9 - (3 + 5) = 1, so we can get [1, 3, 5].
• [1,3,5], 5 - (1 + 3) = 1, so we can get [1, 1, 3].
• [1,1,3], 3 - (1 + 1) = 1, so we can get [1, 1, 1].

Case 2: [1,1,1,2]

• [1,1,1,2], 2 - (1 + 1 + 1) = -1 < 1, invalid, return false.

Case 3: [8,5]

• [8,5], 8 - 5 = 3, so we can get [3,5]
• [3,5], 5 - 3 = 2, so we can get [2,3]
• [2,3], 3 - 2 = 1, so we can get [1,2]
• [1,2], 2 - 1 = 1, so we can get [1,1].

Let sum be the sum of all numbers.

Repeat the following steps:

• Get the largest number n. Update n to be next = n % {sum of all other numbers}, i.e. next = n % (sum - n).
• Decrease sum by n - next.
• Repeat until the sum of all numbers become A.size().

Some corner cases:

1. If sum - n == 1, return true.
2. If n < sum - n, return false.
3. If n % (sum - n) == 0, return false.
// OJ: https://leetcode.com/problems/construct-target-array-with-multiple-sums/

// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
bool isPossible(vector<int>& A) {
if (A.size() == 1) return A[0] == 1;
long sum = accumulate(begin(A), end(A), 0L), N = A.size();
priority_queue<int> pq(begin(A), end(A));
while (sum > N) {
long n = pq.top();
pq.pop();
if (sum - n == 1) return true;
if (n < sum - n) return false;
long next = n % (sum - n);
if (next == 0) return false;
sum -= n - next;
pq.push(next);
}
return true;
}
};


Or

// OJ: https://leetcode.com/problems/construct-target-array-with-multiple-sums/

// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
bool isPossible(vector<int>& A) {
long sum = accumulate(begin(A), end(A), 0L);
priority_queue<int> pq(begin(A), end(A));
while (true) {
long n = pq.top();
pq.pop();
sum -= n;
if (n == 1 || sum == 1) return true;
if (n < sum || sum == 0 || n % sum == 0) return false;
n %= sum;
sum += n;
pq.push(n);
}
}
};


Java

class Solution {
public boolean isPossible(int[] target) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
return num2 - num1;
}
});
int sum = 0;
for (int num : target) {
sum += num;
priorityQueue.offer(num);
}
int length = target.length;
while (sum > length) {
int max = priorityQueue.poll();
int difference = sum - max;
if (difference == 0 || max - difference < 1)
return false;
int prev = max % difference == 0 ? difference : max % difference;
sum -= (max - prev);
priorityQueue.offer(prev);
}
return sum == length;
}
}