Smallest Subset With Greater Sum Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/smallest-subset-with-greater-sum/1

(It is also the problem of the day for 15-September-2022)

Solution:

class Solution { 

    int minSubset(int[] arr,int n) { 

        Arrays.sort(arr);

       long sum=0;

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

           sum=sum+arr[i];

       }

       long sum2=0;

       int index=n-1;

       int count=0;

       while(sum2<=sum){

           sum2=sum2+arr[index];

           sum=sum-arr[index];

           index--;

           count++;

           

       }

       return count;

        

    }

}

Approach :

We want to find out the minimum number of elements such that their sum should be more than the sum of all remaining elements of the array.

So for that, we need to have sum of those elements which are having maximum value, as a result, sum of them will be high and will be less in number as compared to having small value elements and large in number.

So for that, we will apply the following approach:

1. Sort the array.

2. Take the sum of the whole array. (In measure to avoid integer overflow we will use long)

3. Start traversing the array from last till the sum2 becomes more than sum1.{sum2=0 and sum1=sum of array}

    While traversing the array we will count the number of elements also.

4. return the count.

Time Complexity: O(NLOGN)[For Sorting Of Array][GFG Time:1.54]

Space Complexity: O[N][Array is used]

Auxiliary Space: O[1][No additional space is used only constants are used.]

Total Test Cases:1451

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"