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 N 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 <= 10^{5}
0 <= A[i] <= 10^{9}
0 <= B[i] <= 10^{9}
Sum of N over all test cases doesn't exceeds 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def findMinSum(self, A,B,N):

Solutions:
class Solution:

	def findMinSum(self, A, B, N):
		A = sorted(A)
		B = sorted(B)
		ans = 0
		for i in range(N):
			ans += abs(A[i] - B[i])
		return ans


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		s = 0
		for i in range(N):
			s += abs(A[i] - B[i])
		return s


class Solution:

	def findMinSum(self, A, B, N):
		if A is None or B is None:
			return None
		if len(A) != len(B):
			return None
		a = sorted(A)
		b = sorted(B)
		sum = 0
		for i in range(N):
			sum = sum + abs(a[i] - b[i])
		return sum


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		county = 0
		for i in range(0, N, +1):
			county = county + abs(int(A[i]) - int(B[i]))
		return county


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		minimum = 0
		for i in range(0, len(A)):
			minimum = minimum + abs(A[i] - B[i])
		return minimum


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		summ = []
		for i in range(N):
			diff = abs(A[i] - B[i])
			summ.append(diff)
		return sum(summ)


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		res = 0
		for (i, j) in zip(A, B):
			res += abs(i - j)
		return res


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		suma = 0
		for x in range(N):
			suma += abs(A[x] - B[x])
		return suma


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		_sum = 0
		for (a, b) in zip(A, B):
			_sum += abs(a - b)
		return _sum


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		c = 0
		for i in range(N):
			d = abs(A[i] - B[i])
			c += d
		return c


class Solution:

	def findMinSum(self, A, B, N):
		sum = 0
		a = sorted(A)
		b = sorted(B)
		for i in range(N - 1, -1, -1):
			x = a[i]
			y = b[i]
			sum = sum + abs(x - y)
		return sum


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		s = 0
		for i in range(len(A)):
			if A[i] - B[i] >= 0:
				s += A[i] - B[i]
			else:
				s -= A[i] - B[i]
		return s


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		i = j = sum = 0
		while i < N or j < N:
			sum += abs(A[i] - B[j])
			i += 1
			j += 1
		return sum


class Solution:

	def findMinSum(self, A, B, N):
		count = 0
		k = sorted(A)
		l = sorted(B)
		for i in range(N):
			count += abs(k[i] - l[i])
		return count


class Solution:

	def findMinSum(self, A, B, N):
		sum = 0
		A.sort(reverse=False)
		B.sort(reverse=False)
		for i in range(N):
			a = abs(A[i] - B[i])
			sum = sum + a
		return sum


def min_pair_sum(arr_1: [], arr_2: [], n: int):
	arr_1 = sorted(arr_1)
	arr_2 = sorted(arr_2)
	result = 0
	for i in range(0, n):
		diff = arr_1[i] - arr_2[i]
		result = result + abs(diff)
	return result

class Solution:

	def findMinSum(self, A, B, N):
		return min_pair_sum(A, B, N)


class Solution:

	def findMinSum(self, A, B, N):
		A_sort = sorted(A)
		B_sort = sorted(B)
		new_sum = 0
		for i in range(N):
			a = A_sort[i]
			b = B_sort[i]
			new_sum += abs(a - b)
		return new_sum


import math

class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		sumres = 0
		i = 0
		while i < N:
			sumres += math.fabs(A[i] - B[i])
			i += 1
		return int(sumres)


class Solution:

	def findMinSum(self, a, b, n):
		a.sort()
		b.sort()
		s = 0
		for i in range(n):
			if a[i] - b[i] > 0:
				s += a[i] - b[i]
			else:
				s += b[i] - a[i]
		return s


class Solution:

	def findMinSum(self, A, B, N):
		return sum([abs(i - j) for (i, j) in zip(sorted(A), sorted(B))])


class Solution:

	def findMinSum(self, arr1, arr2, N):
		arr1 = sorted(arr1)
		arr2 = sorted(arr2)
		ans = 0
		for i in range(len(arr1)):
			ans += abs(arr1[i] - arr2[i])
		return ans


class Solution:

	def findMinSum(self, a, b, n):
		a.sort()
		b.sort()
		res = [0] * n
		for i in range(n):
			res[i] = abs(a[i] - b[i])
		return sum(res)


import math

class Solution:

	def findMinSum(self, A, B, N):
		A = sorted(A)
		B = sorted(B)
		s = 0
		for i in range(N):
			s = s + math.fabs(A[i] - B[i])
		return int(s)


class Solution:

	def findMinSum(self, A, B, N):
		(a, b) = (A, B)
		n = len(a)
		a.sort()
		b.sort()
		ans = 0
		for i in range(n):
			ans += abs(a[i] - b[i])
		return ans


import numpy as np

class Solution:

	def findMinSum(self, A, B, N):
		y = []
		z = []
		a = sorted(A)
		b = sorted(B)
		c = zip(a, b)
		for i in c:
			d = abs(i[0] - i[1])
			y.append(d)
		return sum(y)


import heapq

class Solution:

	def findMinSum(self, A, B, N):
		heapq.heapify(A)
		heapq.heapify(B)
		cost = 0
		for _ in range(N):
			n1 = heapq.heappop(A)
			n2 = heapq.heappop(B)
			cost += abs(n1 - n2)
		return cost


class Solution:

	def partition(self, arr, l, h):
		pivot = arr[h]
		i = l - 1
		for j in range(l, h):
			if arr[j] <= pivot:
				i += 1
				(arr[i], arr[j]) = (arr[j], arr[i])
		(arr[i + 1], arr[h]) = (arr[h], arr[i + 1])
		return i + 1

	def quicksort(self, arr, l, h):
		if l < h:
			p = self.partition(arr, l, h)
			self.quicksort(arr, l, p - 1)
			self.quicksort(arr, p + 1, h)

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		suma = 0
		for i in range(N):
			suma += abs(A[i] - B[i])
		return suma


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		sum1 = 0
		for i in range(N):
			x = A[i] - B[i]
			if x < 0:
				sum1 += -x
			else:
				sum1 += x
		return sum1


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		(i, j) = (0, 0)
		summ = 0
		while i < N and j < N:
			summ += abs(A[i] - B[j])
			i += 1
			j += 1
		return summ


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		output = 0
		for i in range(N):
			a = abs(A[i] - B[i])
			output += a
		return output


class Solution:

	def findMinSum(self, A, B, N):
		A.sort()
		B.sort()
		s = list(zip(A, B))
		lst = []
		for i in s:
			lst.append(abs(i[0] - i[1]))
		return sum(lst)


class Solution:

	def findMinSum(self, A, B, N):
		l = []
		A.sort()
		B.sort()
		for i in range(len(A)):
			c = A[i] - B[i]
			l.append(abs(c))
		return sum(l)