Construct Target Array With Multiple Sums LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool isPossible(vector<int> &target) {
4
    // Priority queue for storing all the nums in taget in decreasing order.
5
    priority_queue<int> pq;
6
    long long sum = 0; // for storing total sum
7

8
    for (auto num : target) { // adding the nums in pq and sum
9
      pq.push(num);
10
      sum += num;
11
    }
12

13
    // iterating untill all elements in pq become 1 (in turn pq.top() will also
14
    // become 1);
15
    while (pq.top() != 1) {
16
      sum -= pq.top(); // removing the greatest element as it was last upadted
17
                       // when converting [1,1,1...] array to target. So we are
18
                       // left with sum of other elements.
19

20
      // when there are elements greeter than 1 then sum of other elements can
21
      // not be 0 or sum can not be greater than top element because sum + x(any
22
      // number>0) is pq.top().
23
      if (sum == 0 || sum >= pq.top()) return false;
24

25
      // if we delete all copies of sum from pq.top() we get an old element.
26
      int old = pq.top() % sum;
27

28
      // all old elements were > 0 so it can not be 0 unless sum is 1 (This is
29
      // only possible if array has only 2 elements)
30
      if (sum != 1 && old == 0) return false;
31

32
      pq.pop(); // Deleting greatest element
33

34
      pq.push(old); // Adding old element to restore array.
35
      sum += old;   // Updating sum
36
    }
37

38
    // if all elements are 1 then return true
39
    return true;
40
  }
41
};