_1354.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.PriorityQueue;

publicclass_1354 {
publicstaticclassSolution1 {
/*
 * Use % is the key here to avoid TLE, a good test case for this is [1,1000000000]
 */
publicbooleanisPossible(int[] target) {
longsum = 0;
PriorityQueue<Integer> maxHeap = newPriorityQueue<>((a, b) -> b - a);
for (inti = 0; i < target.length; i++) {
maxHeap.offer(target[i]);
sum += target[i];
 }
while (maxHeap.peek() != 1) {
intmax = maxHeap.poll();
sum -= max;
if (max <= sum || sum < 1) {
returnfalse;
 }
max %= sum;
sum += max;
maxHeap.offer(max);
 }
returntrue;
 }
 }
}