1354

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
Explanation: Start with [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 <= 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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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);
        }
    }
};