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

Moderate
0/80
2 upvotes
Asked in companies
AmazonGoogle inc

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2
1 2  
2
1 1
Sample Output 1:
1
2

Sample Output 1 Explanation:

Test case1:

All the possible subsets are:-
{1} → Total weight of balls in subset 1.Sum of weights of remaining balls 2.It is an invalid subset since the weight of balls in the subset is not greater than the weight of the remaining balls.
{2} → Total weight of balls in subset 2.Sum of weights of remaining balls 1. It is a valid subset since the weight of balls in the subset is greater than the weight of the remaining balls.
{1,2} → Total weight of balls in subset 3.Sum of weights of remaining balls 0.It is a valid subset since the weight of balls in the subset is greater than the weight of the remaining balls.

Therefore the minimum subset size is 1.

Test case 2:

All the possible subsets are:-
{1} → Total weight of balls in subset 1.Sum of weights of remaining balls 1.It is an invalid subset since the weight of balls in the subset is not greater than the weight of the remaining balls.
{1,1} → Total weight of balls in subset 2.Sum of weights of remaining balls 0.It is a valid subset since the weight of balls in the subset is greater than the weight of the remaining balls.

Therefore the minimum subset size is 2.
Sample Input 2:
2
7
15 5 11 13 17 10 20
8
1 2 3 4 4 3 2 1
Sample Output 2:
3
3
Hint

Naively iterate over all subsets. 

Approaches (2)
Recursive 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’.

  1. ‘ans’ - stores value to be returned to the user.
  2. ‘arr’ - List of ‘n’ integers containing weight
  3. ‘currIdx’ - Index of the ball for which we need to make a choice to include or not in the subset.
  4. ‘ctr’ - Number of balls that have been taken into a subset.
  5. ‘totalSubsetSum’ - Maintains total weight of balls that have been taken till now.
  6. ‘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’.
Time Complexity

O(‘n*2^n’), where ‘n’ denotes the size of array/list.

 

For an array/list of size ‘n’, we will have ‘2^n’ subsets and we will be iterating through them which gives another factor of ‘n’.

Space Complexity

O(‘n’), where ‘n’ denotes the size of the array/list.

As we recurse we build a stack of ‘n’ size at max.

Code Solution
(100% EXP penalty)
Find the smallest subset of balls whose weight is greater than the weight of the remaining balls.
Full screen
Console