Minimum Difference

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
5 upvotes
Asked in companies
AmazonSoft SuaveJupiter Money

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

2
5 
1 2 3 4 5
1 2 3 4 5
4
4 1 2 4
4 4 4 4

Sample Output 1 :

0 
5

Explanation of Sample Input 1 :

Test Case 1 :  
The energy of attacks of Jiren = [ 1, 2, 3, 4, 5] 
The energy of attacks of Goku = [ 1, 2, 3, 4, 5] 
Here, Goku will not rearrange his attacks.
Energy absorbed by Jiren =  |1 – 1| + |2 – 2| + |2 – 2| + |2 – 2| + |2 – 2|   = 0 
Hence the answer is 0.  

Test Case 2 : 
The energy of attacks of Jiren = [4, 1, 2, 4] 
The energy of attacks of Goku = [4, 4, 4, 4] 
Here, Goku will not rearrange his attacks.
Energy absorbed by Jiren =  |4 – 1| + |4 – 1| + |2 – 4| + |4 – 4| = 5
Hence the answer is 5.

Sample Input 2 :

2
5 
1 2 3 4 5
1 2 10 4 5
4
1 1 5 10
5 8 2 10

Sample Output 2 :

7
8

Explanation of Sample Input 2 :

Test Case 1 :  
The energy of attacks of Jiren = [1, 2, 3, 4, 5] 
The energy of attacks of Goku = [1, 2, 10, 4, 5] 
Here, Goku will rearrange his attacks as [1, 2, 4, 5, 10] 
Energy absorbed by Jiren =  |1 – 1| + |2 – 2| + |3 – 4| + |4 – 5| + |5 – 10|   = 7 
Hence the answer is 7.  

Test Case 2 : 
The energy of attacks of Jiren = [1, 1, 5, 10] 
The energy of attacks Goku = [5, 8, 2, 10] 
Here Goku will rearrange his attacks as [2, 5, 8, 10] 
Energy absorbed by Jiren =  |1 – 2| + |1 – 5| + |5 – 8| + |10 – 10| = 8 
Hence the answer is 8.
Hint

For each attack of Jiren try to find the attack of Goku which is giving the minimum absolute difference with it. 

Approaches (1)
Greedy Approach

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’.
Time Complexity

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

 

Sorting both arrays ‘A’ and ‘B’ takes O(N * log(N) ) time. Also, we are using a loop to calculate the answer that takes O(N) time. 
Hence, the overall time complexity will be O( N * log(N) ) + O(N) = O( N * log(N) ).

Space Complexity

O(1). 

 

No extra space is being used.

Code Solution
(100% EXP penalty)
Minimum Difference
Full screen
Console