Minimum Subsequence in Non-Increasing Order

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes

Problem statement

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

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

Sample Input 1 :

2
2
7 11
4
2 3 7 3

Sample output 1 :

11
7 3

Explanation of Sample output 1 :

For the first test case, subsequence [11] is minimal such that the sum of its elements is strictly greater than the elements not included.

For the second test case, subsequences [7, 3], [2, 7]  are minimal such that the sum of their elements are strictly greater than the elements not included. But [7, 3] has the maximum sum so the answer will be [7, 3].

Sample Input 2 :

2
1
3
5
4 4 7 6 7

Sample output 2 :

3
7 7 6

Explanation of Sample output 2 :

For the first test case, subsequence [3] is minimal such that the sum of its elements is strictly greater than the elements not included.

For the second test case, subsequence [7, 6, 7] is the desired subsequence having the sum of its elements strictly greater than the sum of the elements not included.
Hint

Can sorting help?

Approaches (1)
Sorting

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:

 

  1. Sort the elements of the given array/list in non-increasing order.
  2. Create a variable called 'SUM' and store the sum of each element.
  3. 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.
  4. 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.
  5. Return the 'ANS' which denotes the expected subsequence.
Time Complexity

O(N * log(N)), where ‘N’ is the length of the given array/list.

 

Since we are sorting the given array/list which takes O(N * log(N)) and then iterating through it twice which takes O(N) time. So, the overall time complexity will be 2 * O(N) + O(N * log(N)) = O(N * log(N)).

Space Complexity

O(N), where ‘N’ is the length of the given array/list.

 

Since we are storing the subsequence in an array/list where it will contain O(N) elements. So, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Minimum Subsequence in Non-Increasing Order
Full screen
Console