Team Formation

Easy
0/40
profile
Contributed by
1 upvote
Asked in company
Infineon Technologies

Problem statement

You are giving an interview, and you need to prove your intelligence. You will be given an array/list ‘ARR’ of ‘N’ positive integers, which are the runs scored by ‘N’ best players in the world in their last innings. You will be given ‘X’, which is the target you need to come near with the help of two other players in the array. You scored only 30 runs and gave rest runs to your other two friends. In short, you need to find two players, and the total runs scored by them in their respective last innings should be less than or equal to ‘X - 30’.

Example: Given an ‘ARR’: [ 30, 40, 10, 8, 60, 100, 40 ] and given ‘X’ is 110. The output array/list which will be printed is [ 40, 40 ].

Note: There might be many different output arrays/lists possible like [ 30, 40 ], [ 40, 40 ], or [ 40, 10 ], but you need to print which makes the highest runs amongst them.

Note: There always exists a pair in ‘ARR’ that has the sum less than or equal to ‘X - 30’ and the second integer must be larger than the first integer.

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 will contain one integer ‘N’ and ‘X’, that denotes the size of the ‘ARR’ and runs you need to come close to with the help of your team.

The second line of each test case contains ‘N’ space-separated integers ‘ARR[i]’, which denoting the numbers present in our ‘ARR’.
Output Format: 
For each test case, return a pair of integers denoting the closest pairs of values which have the highest runs combined.

Output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of.
Constraints: 
1 <= T <= 5
1 <= N <= 10^5
0 <= A[i], X <= 10^9

Time Limit: 1 sec
Sample Input 1:
2
6 140
50 20 35 110 150 45
5 150
50 70 35 100 50
Sample Output 1:
45 50
50 70
Explanation For Sample Input 1:
In the first test case, the possible pairs of answers are [ 50, 20], [ 50, 35], [ 50, 45],  [ 20, 35], [ 20, 45], and  [ 35, 45]. But the closest we can come to ‘X’ can be achieved by the pair [ 50, 45] as the sum of them is 95 while the rest are smaller than it.

In the second test case, the possible pairs of answers are [ 50, 70], [ 50, 35], [ 50, 50],  [ 70, 35], and  [ 35, 50]. But the closest we can come to ‘X’ can be achieved by the pair [ 50, 70] as the sum of them is 110 while the rest are smaller than it.
Sample Input 2:
2
2 140
5 10
5 130
80 120 35 25 75
Sample Output 2:
5 10
25 75
Explanation For Sample Input 2:
In the first test case, there is only one pair [5,10] which gives the sum less than or equal to 110.
In the second test case also there is only one pair [25,75] which gives the sum less than or equal to 100. So, we will return [25, 75].
Hint

Can you think of checking all the pairs one by one?

Approaches (2)
Brute Force

The basic idea of this approach is to iterate the whole ‘ARR’ from start and check for all the elements present after it. If the sum of the current pair is less than or equal to ‘X’ minus 30 then we will check if it is less than our temporary answer or not. If it is less then we will replace it with a temporary answer.
 

Here is the algorithm:
 

  1. Declare a temporary array/list variable ‘ANS’ in which we store our answer and initialize -1.
  2. Run a loop for ‘i’ = 0  to ‘N’ - ’:
    • Run  a loop for ‘j’ = ‘i’ + 1 to ‘N’ - 1:
      • Check if the sum of ‘ARR[i]’ and ‘ARR[j]’ is greater than ‘ANS[0]’ and ‘ANS[1]’ and less than or equal to ‘X’ - 30:
        • If both the conditions are satisfied then reassign the values of both variables of ‘ANS’ to ‘ARR[i]’ and ‘ARR[j]’.
  3. Finally, return ‘ANS’.
Time Complexity

O(N^2), where N is the number of elements in the given ‘ARR’.

 

Because every time for all the elements present in ‘ARR’, we will check for all the possible pairs present in ‘ARR’ and thus, we need to run two for loops. Thus, the time complexity is O(N^2).

Space Complexity

O(1)

 

Because we are not using any extra space for finding our answer.

Code Solution
(100% EXP penalty)
Team Formation
Full screen
Console