Last Updated: 17 Feb, 2021

Find the smallest subset of balls whose weight is greater than the weight of the remaining balls.

Moderate

Asked in companies

Solve now

Problem statement

You have been given an array/list ‘arr’ of integers consisting of ‘n’ integers which are the weight of ‘n’ balls. Your task is to return the size of the smallest subset of balls whose weight is greater than the weight of the remaining balls.

Example:

You have 3 balls of weight 1, 2, and 3. You can take subset (1, 3) or (2, 3) as their total weight is greater than the weight of the remaining balls. The answer will be 2.

subsequence

Green balls are taken in a subset.

Note:

You do not need to print anything; it has already been taken care of. Just implement the function.

Input Format:

The first line contains a single integer ‘t’ representing the number of test cases.

The first line of each test case contains a single integer ‘n’ representing the size of the array/list.

The second line and the last line of input contains ‘n’ single space-separated integers representing the array/list elements.

Output Format:

For each test case return the size of the smallest subset.

Constraints:

1 <= T <= 10
1 <= N <= 1000
1 <= ‘arr[i]’ <= 10^6

Where ‘T’ is the number of test cases.‘N’ is the number of elements in the array/list. ‘arr[i]’ is the weight of the ith ball.  

Time Limit: 1sec

Solve now

Approaches

01 Approach

We have a simple recursion to solve this problem. Since the sum of all the balls remains constant we will just maintain the sum of weights of balls that we have taken in the subset.

We can declare ‘ans’, ‘arr’ and ‘totalSum’ as global variables.

We will define a recursive function with parameters ‘currIdx’, ‘totalSubsetSum’, and ‘ctr’.

‘ans’ - stores value to be returned to the user.
‘arr’ - List of ‘n’ integers containing weight
‘currIdx’ - Index of the ball for which we need to make a choice to include or not in the subset.
‘ctr’ - Number of balls that have been taken into a subset.
‘totalSubsetSum’ - Maintains total weight of balls that have been taken till now.
‘totalSum’ - Stores total weight of all the balls.

We will call recursive function subsetIteration(‘currIdx’, ‘totalSubsetSum’ , ‘ctr’ , ‘n’ , ‘arr’) with (0,0,0,n,arr) as we will start from the 1st ball at 0th position. Since no elements have been taken into subset yet, the total subset-sum and number of balls is zero.
At each particular curr_idx in recursion do as follows:-
- If ‘currIdx’== ‘n’ We have reached the end of the list. Check if ‘totalSubsetSum’ is greater than the sum of the remaining elements (‘totalSum’-‘totalSubsetSum’). If yes then update ‘ans’ with min(‘ans’, ‘ctr’).
Else There are two cases:-
We take the current element in subset and recursively call subsetIteration(‘currIdx’+1, ‘totalSubsetSum’+ ‘arr[currIdx]’ ,‘ctr’+1 , ‘n’ , ‘arr’)
We don’t take current element in subset and recursively call
subsetIteration(‘currIdx’+1, ‘totalSubsetSum’, ‘ctr’ , ‘n’ , ‘arr’)
Return ‘ans’.

Solve now

02 Approach

Adding a ball to a subset increases subset size by 1.So it is optimal for us to choose the maximum weight ball which has not yet been taken into the subset. Therefore we are taking balls in our subset in order of decreasing weights. So we will arrange balls according to their weight using a sort function. Now iterate from the end (i.e. maximum weight). Add a current ball to ‘totalSubsetSum’ and increase counter i.e ans as the size of the subset increases. If this subset-sum is greater than the remaining elements break and come out of the loop and display the ans.

Following is the algorithm for this approach:

Sort the list of weights of balls.
Initialize ‘ans’ and ‘totalSubsetSum’ with 0.
We iterate from ‘n’-1 to 0
In each iteration:-
- We add the current iteration ball to our subset:-
  - ‘totalSubsetSum’ += ‘arr’[i]
  - ‘ans’++
- We check if ‘totalSubsetSum’ is greater than the sum of the remaining elements (‘totalSum’-‘totalSubsetSum’). If true we break and come out of the loop.
Finally, we return ‘ans’ as result.

Solve now