classSolution{public:boolisPossible(vector<int>&target){if(target.size()==1)returntarget[0]==1;longsum=accumulate(target.begin(),target.end(),0L);priority_queue<int>maxHeap;for(constintnum:target)maxHeap.push(num);while(maxHeap.top()>1){constlongmx=maxHeap.top();maxHeap.pop();constlongrestSum=sum-mx;// Only occurs if n == 2.if(restSum==1)returntrue;constlongupdated=mx%restSum;// updated == 0 (invalid) or didn't change.if(updated==0||updated==mx)returnfalse;maxHeap.push(updated);sum=sum-mx+updated;}returntrue;}};
classSolution{publicbooleanisPossible(int[]target){if(target.length==1)returntarget[0]==1;longsum=Arrays.stream(target).asLongStream().sum();Queue<Integer>maxHeap=newPriorityQueue<>(Collections.reverseOrder());for(finalintnum:target)maxHeap.offer(num);while(maxHeap.peek()>1){finallongmx=maxHeap.poll();finallongrestSum=sum-mx;// Only occurs if n == 2.if(restSum==1)returntrue;finallongupdated=mx%restSum;// updated == 0 (invalid) or didn't change.if(updated==0||updated==mx)returnfalse;maxHeap.offer((int)updated);sum=sum-mx+updated;}returntrue;}}
1 2 3 4 5 6 7 8 91011121314151617181920212223
classSolution:defisPossible(self,target:list[int])->bool:iflen(target)==1:returntarget[0]==1summ=sum(target)maxHeap=[-numfornumintarget]heapq.heapify(maxHeap)while-maxHeap[0]>1:mx=-heapq.heappop(maxHeap)restSum=summ-mx# Only occurs if n == 2.ifrestSum==1:returnTrueupdated=mx%restSum# updated == 0 (invalid) or didn't change.ifupdated==0orupdated==mx:returnFalseheapq.heappush(maxHeap,-updated)summ=summ-mx+updatedreturnTrue
Thanks for stopping by! If you find this site helpful, consider buying me some protein powder to keep me fueled! π