[Leetcode] Problem 1354 - Construct Target Array With Multiple Sums

Posted on | In ,

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

No.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

No.2

Input: target = [1,1,1,2]

Output: false

Explanation: Impossible to create target array from [1,1,1,1].

No.3

Input: target = [8,5]

Output: true

Constraints

  • N == target.length
  • 1 <= target.length <= 5 * 10^4
  • 1 <= target[i] <= 10^9

Code

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
// m = k * rest + r, m > rest => r = m % rest
public boolean isPossible(int[] target) {
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    long sum = 0;

    for (int t : target) {
        pq.offer(t);
        sum += t;
    }

    while (true) {
        int m = pq.poll();
        sum -= m;

        if (m == 1 || sum == 1) // [1, m]
            return true;
        if (sum == 0 || m <= sum) // [m] or [1, 1, 2]
            return false;

        int r = m % (int) sum;

        if (r == 0) // [x, y, k * (x + y)]
            return false;

        pq.offer(r);
        sum += r;
    }
}