package com.fishercoder.solutions;

import java.util.Collections;
import java.util.PriorityQueue;

public class _1354 {
    public static class Solution1 {
        /**
         * 1. A good idea/trick to calculate the previous value of the largest number max: (2 * max - total).
         * 2. Use a PriorityQueue to store the elements in reverse order to help us get the largest element in O(1) time
         * 3. Also keep a variable of total sum
         * <p>
         * reference: https://leetcode.com/problems/construct-target-array-with-multiple-sums/discuss/510214/C%2B%2B-Reaching-Points-Work-Backwards
         */
        public boolean isPossible(int[] target) {
            PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
            long sum = 0L;
            for (int v : target) {
                sum += v;
                pq.offer((long) v);
            }
            while (sum > pq.size()) {
                long max = pq.poll();
                Long prev = 2 * max - sum;
                if (prev < 1) {
                    return false;
                }
                pq.offer(prev);
                sum -= max;
                sum += prev;
            }
            return sum == pq.size();
        }
    }
}
@@ -33,38 +33,8 @@
 s;%0A%0A
-import java.util.Collections;%0A
 impo
@@ -146,709 +146,387 @@
   * 
-1. A good idea/trick to calculate the previous value of the largest number max: (2 * max - total).%0A         * 2. Use a PriorityQueue to store the elements in reverse order to help us get the largest element in O(1) time%0A         * 3. Also keep a variable of total sum%0A         * %3Cp%3E%0A         * reference: https://leetcode.com/problems/construct-target-array-with-multiple-sums/discuss/510214/C%252B%252B-Reaching-Points-Work-Backwards%0A         */%0A        public boolean isPossible(int%5B%5D target) %7B%0A            PriorityQueue%3CLong%3E pq = new PriorityQueue%3C%3E(Collections.reverseOrder());%0A            long sum = 0L;%0A            for (int v : target) %7B%0A                sum += v;%0A                pq.offer((long) v)
+Use %25 is the key here to avoid TLE, a good test case for this is %5B1,1000000000%5D%0A         */%0A        public boolean isPossible(int%5B%5D target) %7B%0A            long sum = 0;%0A            PriorityQueue%3CInteger%3E maxHeap = new PriorityQueue%3C%3E((a, b) -%3E b - a);%0A            for (int i = 0; i %3C target.length; i++) %7B%0A                maxHeap.offer(target%5Bi%5D);%0A                sum += target%5Bi%5D
 ;%0A  
@@ -560,23 +560,27 @@
 le (
-sum %3E pq.size()
+maxHeap.peek() != 1
 ) %7B%0A
@@ -599,21 +599,25 @@
     
-long
+int
  max = 
+maxHea
 p
-q
 .pol
@@ -641,33 +641,18 @@
     
-Long prev = 2 * max - sum
+sum -= max
 ;%0A  
@@ -669,20 +669,33 @@
     if (
-prev
+max %3C= sum %7C%7C sum
  %3C 1) %7B%0A
@@ -766,22 +766,18 @@
     
-pq.offer(prev)
+max %25= sum
 ;%0A  
@@ -786,33 +786,33 @@
             sum 
--
++
 = max;%0A         
@@ -822,19 +822,26 @@
     
-sum += prev
+maxHeap.offer(max)
 ;%0A  
@@ -875,24 +875,12 @@
 urn 
-sum == pq.size()
+true
 ;%0A  

refactor 1354