Adding Array Elements Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/adding-array-element4756/1

Solution:

int minOperations(int[] arr, int n, int k) {

        Arrays.sort(arr);

        PriorityQueue<Integer>pq=new PriorityQueue<Integer>();

        for(int i=0;i<n;i++){

            pq.add(arr[i]);

        }

        if(pq.peek()>=k){

            return 0;

        }

        else{

            int count=0;

            //int d=pq.peek();

            while(pq.peek()<k){

                int a=pq.remove();

                int b=pq.remove();

                //System.out.println("after removal: "+pq);

                pq.add(a+b);

               // System.out.println("After addition: "+pq);

                count++;

            }

            return count;

        }

Time Complexity: O(NLogN)[Array sort is there.[GFG Time:1.2/8.1]

Space Complexity:O(N)[Array is given]

Auxiliary Space: O(N)[In start PriorityQueue will have all elements of the array.]

Total Test Cases:61

Approach Used:

Here first we will sort the array so we get the minimum element at the start and maximum element in end.

Later we only need to see that the start element is lower or more than k.

So for that, we will traverse the array and get starting two elements and add their result in the queue.

Priority queue will automatically sort the values and give the peek as a minimum element of all those elements present in the queue. If that value is more than k then we need to break and hence return count otherwise we will traverse till we get a peek of queue more than k or equal to k.

Usage or PriorityQueue is preferred over the set as both do automatically sort but in set duplicates will not be there however we need to take care of duplicates also. 

So PriorityQueue is preferred.

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"