Welcome to Subscribe On Youtube

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
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/
// 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);
        }
    }
};

  • 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;
    }
}

  • // 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;
    }
};

All Problems

All Solutions