Last Updated: 19 Apr, 2021
Minimum Subsequence in Non-Increasing Order
Easy
You have been an array/list “ARR” of integers. Now, you are supposed to find a subsequence of minimum length such that the sum of elements in the subsequence is strictly greater than the sum of the rest of the elements.
Please note that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements.
Note:
If there are multiple solutions, then find the subsequence with the maximum total sum. Also, assume that there will be a unique solution.
Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first input line of each test case contains an integer ‘N’ denoting the number of elements in the given array/list.
The second input line of each test case contains ‘N’ space-separated integers denoting the elements of the “ARR”.
Output Format :
For each test case, print the space-separated integers denoting the elements of the desired subsequence in non-increasing order.
Print the output of each test case in a separate line.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 50
1 <= N <= 10000
1 <= ARR[i] <= 10000
Where ARR[i] denotes the i-th element of the given array/list.
Time limit: 1 sec
Approaches
The key idea of this approach is to sort the elements of the given array/list in non-increasing order. Since we are looking for the subsequence having a minimum length such that the sum of its elements is strictly greater than the sum of the rest of the elements, we will choose elements from the front of the sorted array/list greedily. This will ensure that we are selecting the minimum possible elements for getting any sum.
Now, consider the following steps:
- Sort the elements of the given array/list in non-increasing order.
- Create a variable called 'SUM' and store the sum of each element.
- Create a variable called 'CUR_SUM' to store the sum of the elements of subsequence which we will be choosing. Also, create an empty array/list 'ANS' to store the elements of that subsequence.
- Now, start iterating through the array/list from the front:
- If 'CUR_SUM' > 'SUM' - 'CUR_SUM' then break the loop because we have got the subsequence whose length is minimum and the sum of its elements is strictly greater than the rest of the elements.
- Otherwise, add the current element in the subsequence. And update the 'CUR_SUM' accordingly.
- Return the 'ANS' which denotes the expected subsequence.