Last Updated: 24 May, 2021
Team Formation
Easy
Asked in company
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.
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
Approaches
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:
- Declare a temporary array/list variable ‘ANS’ in which we store our answer and initialize -1.
- 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]’.
- 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:
- Run a loop for ‘j’ = ‘i’ + 1 to ‘N’ - 1:
- Finally, return ‘ANS’.
The basic idea of this approach is to initially sort the whole ‘ARR’ and then using two pointers we will try to get all the nearby possible pairs giving sum ‘X’ - 30. With the help of a two pointer approach, we will get only valid nearby possible pairs and thus, iterating two loops can be reduced to one loop.
Here is the algorithm:
- Declare a temporary array/list variable ‘ANS’ in which we store our answer and initialize -1.
- Declare two variables ‘i’ and ‘j’ pointing to the first and the last index of ‘ARR’ respectively and sort the entire ‘ARR’.
- While the value of ‘i’ is less than ‘j’ we will run a loop that will help us to find the possible pairs:
- Declare a variable ‘CURRENT_SUM’ which will have the sum of ‘ARR[i]’ and ‘ARR[j]’.
- If ‘CURRENT_SUM’ is less than or equal to ‘X’ - 30:
- We will check if ‘CURRENT_SUM’ is higher than the sum of ‘ANS[0]’ and ‘ANS[1]’ and replace them with ‘ARR[i]’ and ‘ARR[j]’ if they are higher.
- Increment ‘i’ by 1.
- Else we know that it is not a required pair and thus, we will decrement the value of ‘j’ by 1.
- Finally, return ‘ANS’.