aboutsummaryrefslogtreecommitdiff
path: root/other/construct_array_multiple_sum.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/construct_array_multiple_sum.cpp')
-rw-r--r--other/construct_array_multiple_sum.cpp30
1 files changed, 30 insertions, 0 deletions
diff --git a/other/construct_array_multiple_sum.cpp b/other/construct_array_multiple_sum.cpp
new file mode 100644
index 0000000..5d2751d
--- /dev/null
+++ b/other/construct_array_multiple_sum.cpp
@@ -0,0 +1,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);
+}