Last Updated: 11 Feb, 2021
Minimum Difference
Moderate
Asked in companies
Goku is fighting Jiren in “Tournament of Power”. If Goku loses then Universe 7 will get destroyed by Zeno but if Jiren loses then Universe 11 will get destroyed and Universe 7 will survive. Both Goku and Jiren launched ‘N’ attacks towards each other. Each attack has some energy. Jiren has a special ability through which he can absorb the attacks of Goku. If Goku launches an attack with energy ‘A’ and Jiren launches an attack with energy ‘B’ then
If ‘A’ > ‘B’, then Goku’s attack will destroy Jiren’s attack but Jiren will absorb Goku’s attack and absorb energy = ‘A’ – ‘B’.
If ‘A’ < ‘B’, then Jiren’s attack will destroy Goku’s attack and Jiren will absorb the remaining energy of his attack which is equal to = ‘B’ – ‘A’.
If ‘A’ == ‘B’, then both Goku’s and Jiren’s attack will get destroyed and Jiren will not absorb any energy.
Goku finds out the energy of all attacks of Jiren and the order in which Jiren is going to attack with the help of Whis. As Jiren becomes powerful by absorbing energy, Goku wants to minimize the total energy absorbed by Jiren by rearranging the order of his attacks.
As Goku is busy fighting with Jiren, he called you for help.
The fate of Universe 7 lies in your hand.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains an integer ‘N’. Here ‘N’ represents the total number of attacks used by Goku and Jiren.
The second line contains ‘N’ space-separated integers denoting the energy of attacks of Jiren.
The third line contains ‘N’ space-separated integers denoting the energy of attacks of Goku.
Output Format :
For each test case, print the minimum energy which Jiren will absorb.
The output of each test case will be printed in a separate line.
Constraints :
1 <= T <= 5
1 <= N <= 5000
1 <= data <= 10^9
Where ‘T’ is the number of test cases, ‘N’ denotes the total number of attacks to be used by Goku and Jiren and ‘data’ denotes the energy of attack of Goku and Jiren.
Time Limit: 1sec
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Approaches
Let’s represent the energy of Goku’s attack by array ‘A’ and energy of Jiren’s attack with ‘B’. First, we will sort both arrays ‘A’ and ‘B’. Then, for each element of ‘A’, say ‘X’ we fill find an element in ‘B’, say ‘Y’ such that |X – Y| is minimum. For the first element of ‘A’ i.e. ‘A[0]’, we need to pair it with ‘B[0]’ because all elements with index ‘i’ such that ‘i’ > 0 will give |A[0] – B[i]| and this absolute difference is greater than | A[0] – B[0] |
So, for each index ‘i’ we need to pair ‘A[i]’ with ‘B[i]’.
Algorithm :
- Declare a variable to store the minimum sum of absolute difference, say ‘answer’.
- Sort array ‘A’ and array ‘B’.
- Run a loop from ‘i’ = 0 to ‘N’.Here ‘N’ is the length of array ‘A’.
- Add the absolute of ‘A[i] – B[i]’ to answer.
- Finally, return the ‘answer’.