Skip to content

Latest commit

 

History

History

Minimum Sum of Absolute Differences of Pairs - GFG

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

Minimum Sum of Absolute Differences of Pairs

Easy

You are given two arrays A and B of equal length N. Your task is to pair each element of array A to an element in array B, such that the sum of the absolute differences of all the pairs is minimum.

Example 1:

Input:
N = 4
A = {4,1,8,7}
B = {2,3,6,5}
Output:
6
Explanation:
If we take the pairings as (1,2), (4,3),
(7,5), and (8,6), the sum will be S =
|1 - 2| + |4 - 3| + |7 - 5| + |8 - 6| = 6.
It can be shown that this is the minimum sum we can get.

 

Example 2:

Input:
N = 3
A = {4,1,2}
B = {2,4,1}
Output:
0
Explanation:
If we take the pairings as (4,4), (1,1), and
(2,2), the sum will be S = |4 - 4| + |1 - 1| +
|2 - 2| = 0. It can be shown that this is the
minimum sum we can get.

 

Your Task:

You don't need to read input or print anything. Your task is to complete the function findMinSum() which takes the arrays A[], B[], and its size as inputs and returns the minimum sum of the absolute differences of the pairs.

 

Expected Time Complexity: O(N*log(N))
Expected Auxiliary Space: O(1)

 

Constraints:
1 <= N <= 105
0 <= A[i] <= 109
0 <= B[i] <= 109
Sum of N over all test cases doesn't exceeds 106