11package com .fishercoder .solutions ;
22
3- import java .util .Collections ;
43import java .util .PriorityQueue ;
54
65public class _1354 {
76public static class Solution1 {
87/**
9- * 1. A good idea/trick to calculate the previous value of the largest number max: (2 * max - total).
10- * 2. Use a PriorityQueue to store the elements in reverse order to help us get the largest element in O(1) time
11- * 3. Also keep a variable of total sum
12- * <p>
13- * reference: https://leetcode.com/problems/construct-target-array-with-multiple-sums/discuss/510214/C%2B%2B-Reaching-Points-Work-Backwards
8+ * Use % is the key here to avoid TLE, a good test case for this is [1,1000000000]
149 */
1510public boolean isPossible (int []target ) {
16- PriorityQueue < Long > pq =new PriorityQueue <>( Collections . reverseOrder ()) ;
17- long sum =0L ;
18- for (int v : target ) {
19- sum += v ;
20- pq . offer (( long ) v ) ;
11+ long sum =0 ;
12+ PriorityQueue < Integer > maxHeap =new PriorityQueue <>(( a , b ) -> b - a ) ;
13+ for (int i = 0 ; i < target . length ; i ++ ) {
14+ maxHeap . offer ( target [ i ]) ;
15+ sum += target [ i ] ;
2116 }
22- while (sum > pq . size () ) {
23- long max =pq .poll ();
24- Long prev = 2 * max - sum ;
25- if (prev <1 ) {
17+ while (maxHeap . peek () != 1 ) {
18+ int max =maxHeap .poll ();
19+ sum -= max ;
20+ if (max <= sum || sum <1 ) {
2621return false ;
2722 }
28- pq . offer ( prev ) ;
29- sum - =max ;
30- sum += prev ;
23+ max %= sum ;
24+ sum + =max ;
25+ maxHeap . offer ( max ) ;
3126 }
32- return sum == pq . size () ;
27+ return true ;
3328 }
3429 }
3530}