aboutsummaryrefslogtreecommitdiff
path: root/construct_array_multiple_sum.cpp
blob: 5d2751dc3c0362edd0f8522e67152f89a176e81b (plain)
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
29
30
#include "leetcode.h"

class Solution {
public:
  bool isPossible(vector<int> &target) {
    long total = 0;
    int i;
    priority_queue<int> pq(target.begin(), target.end());
    for (int i : target)
      total += i;
    while (true) {
      i = pq.top();
      pq.pop();
      total -= i;
      if (i == 1 || total == 1)
        return true;
      if (i < total || total == 0 || i % total == 0)
        return false;
      i %= total;
      total += i;
      pq.push(i);
    }
  }
};

int main() {
  Solution obj;
  vector<int> target = {9, 3, 5};
  cout << obj.isPossible(target);
}