Given two arrays A[] and B[] of size N, the task is to find the maximum possible sum of abs(A[i] – B[i]) by rearranging the array elements.
Examples:
Input: A[] = {1, 2, 3, 4, 5}, B[] = {1, 2, 3, 4, 5}
Output: 12
Explanation:
One of the possible rearrangements of A[] is {5, 4, 3, 2, 1}.
One of the possible rearrangements of B[] is {1, 2, 3, 4, 4}.
Therefore, the sum of all possible values of abs(A[i] – B[i]) = { abs(5 – 1) + abs(4 – 2) + abs(3 – 3) + abs(2 – 4) + abs(1 – 5) } = 12Input: A[] = {1, 2, 2, 4, 5}, B[] = {5, 5, 5, 6, 6}
Output: 13
Explanation:
One of the possible rearrangements of A[] is {5, 4, 2, 2, 1}.
One of the possible rearrangements of B[] is {5, 5, 5, 6, 6}.
Therefore, the sum of all possible values of abs(A[i] – B[i]) = { abs(5 – 5) + abs(4 – 5) + abs(2 – 5) + abs(2 – 6) + abs(1 – 6) } = 13
Approach: Follow the steps below to solve the problem:
- Sort the array A[] in ascending order.
- Sort the array B[] in descending order.
- Traverse both the arrays and print the sum of all possible value of abs(A[i] – B[i]).
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum possible sum// by rearranging the given array elementsint MaxRearrngeSum(int A[], int B[], int N){ // Sort the array A[] // in ascending order sort(A, A + N); // Sort the array B[] // in descending order sort(B, B + N, greater<int>()); // Stores maximum possible sum // by rearranging array elements int maxSum = 0; // Traverse both the arrays for (int i = 0; i < N; i++) { // Update maxSum maxSum += abs(A[i] - B[i]); } return maxSum;}// Driver Codeint main(){ int A[] = { 1, 2, 2, 4, 5 }; int B[] = { 5, 5, 5, 6, 6 }; int N = sizeof(A) / sizeof(A[0]); cout<< MaxRearrngeSum(A, B, N); return 0;} |
Java
// Java program to implement // the above approach import java.lang.Math;import java.util.Arrays; import java.util.Collections; class GFG{ // Function to find the maximum possible sum // by rearranging the given array elements static int MaxRearrngeSum(Integer A[], Integer B[], int N) { // Sort the array A[] // in ascending order Arrays.sort(A); // Sort the array B[] // in descending order Arrays.sort(B, Collections.reverseOrder()); // Stores maximum possible sum // by rearranging array elements int maxSum = 0; // Traverse both the arrays for(int i = 0; i < N; i++) { // Update maxSum maxSum += Math.abs(A[i] - B[i]); } return maxSum; } // Driver codepublic static void main (String[] args){ Integer A[] = { 1, 2, 2, 4, 5 }; Integer B[] = { 5, 5, 5, 6, 6 }; int N = A.length; System.out.println(MaxRearrngeSum(A, B, N)); }}// This code is contributed by ujjwalgoel1103 |
Python3
# Python3 program to implement# the above approach# Function to find the maximum possible sum# by rearranging the given array elementsdef MaxRearrngeSum(A, B, N): # Sort the array A[] # in ascending order A.sort() # Sort the array B[] # in descending order B.sort(reverse = True) # Stores maximum possible sum # by rearranging array elements maxSum = 0 # Traverse both the arrays for i in range(N): # Update maxSum maxSum += abs(A[i] - B[i]) return maxSum# Driver Codeif __name__ == "__main__": A = [ 1, 2, 2, 4, 5 ] B = [ 5, 5, 5, 6, 6 ] N = len(A) print(MaxRearrngeSum(A, B, N))# This code is contributed by chitranayal |
C#
// Java program to implement // the above approach using System;class GFG{ // Function to find the maximum possible sum // by rearranging the given array elements static int MaxRearrngeSum(int []A, int []B, int N) { // Sort the array A[] // in ascending order Array.Sort(A); // Sort the array B[] // in descending order Array.Sort(B); Array.Reverse(B); // Stores maximum possible sum // by rearranging array elements int maxSum = 0; // Traverse both the arrays for(int i = 0; i < N; i++) { // Update maxSum maxSum += Math.Abs(A[i] - B[i]); } return maxSum; } // Driver codepublic static void Main(){ int []A = { 1, 2, 2, 4, 5 }; int []B = { 5, 5, 5, 6, 6 }; int N = A.Length; Console.WriteLine(MaxRearrngeSum(A, B, N)); }}// This code is contributed by ipg2016107 |
Javascript
<script>// javascript program for the// above approach// Function to find the maximum possible sum// by rearranging the given array elementsfunction MaxRearrngeSum(A, B, N){ // Sort the array A[] // in ascending order A.sort(); // Sort the array B[] // in descending order B.sort(); B.reverse(); // Stores maximum possible sum // by rearranging array elements let maxSum = 0; // Traverse both the arrays for(let i = 0; i < N; i++) { // Update maxSum maxSum += Math.abs(A[i] - B[i]); } return maxSum;} // Driver Code let A = [ 1, 2, 2, 4, 5 ]; let B = [ 5, 5, 5, 6, 6 ]; let N = A.length; document.write(MaxRearrngeSum(A, B, N)); </script> |
Output:
13
Time Complexity: O(N * Log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
