Given two arrays a[] and b[] of equal size. The task is to calculate the minimum sum of absolute differences for each index. It is allowed to replace at most 1 element of the first array with any value from the first array itself.
Example:
Input: a[] = {1, 9, 4, 2}, b[] = {2, 3, 7, 1}
Output: 6
Explanation: Change the value of a[1] = 4 or 2. The minimum absolute difference will be |1-2| + |4-3| + |4-7| + |2-1| = 6.Input: a[] = {1, 6, 4, 9}, b[] = {1, 6, 4, 9}
Output: 0
Explanation: There is no need to change any element.
Approach: This problem can be solved by using the Greedy Approach and Binary Search. Follow the below steps to solve the problem:
- First calculate a variable sum = 0, that will store the initial absolute difference for each index between arrays a[] and b[].
- Iterate in the range [0, n] and increment sum += abs(a[i] – b[i]).
- Make new vector nums that will store elements of a[] in sorted order.
- Now iterate from 0 to N-1 and for each element try to replace the value of a[i] to the closest possible value to b[i] from the array a[].
- The above closest value can be found quickly with binary search
- Use std::lower_bound function to find closest value.
- Update the minimum possible answer after trying for each iteration.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum sum absolute// difference from two arraysint minAbsoluteDiffSum(int a[], int b[], int n){ // Variable to store the // initial absolute difference sum int sum = 0; // Make another vector to // store the elements of a in // sorted order vector<int> nums(n); for (int i = 0; i < n; i++) { nums[i] = a[i]; sum += abs(a[i] - b[i]); } // Variable to store the minimum sum int min_answer = sum; // Sort the copy array of a sort(nums.begin(), nums.end()); for (int i = 0; i < n; i++) { // Binary Search for elements // just greater than b[i]. int it = lower_bound(nums.begin(), nums.end(), b[i]) - nums.begin(); // Take minimum from just // greater and less than b[i]. int cur = min( abs(nums[min(it, (n - 1))] - b[i]), abs(nums[max(0, it - 1)] - b[i])); // update the minimum answer if (cur < abs(a[i] - b[i])) { min_answer = min( min_answer, sum - abs(a[i] - b[i]) + cur); } } return min_answer;}// Driver Codeint main(){ int a[] = { 1, 9, 4, 2 }; int b[] = { 2, 3, 7, 1 }; int N = sizeof(a) / sizeof(a[0]); cout << minAbsoluteDiffSum(a, b, N);} |
Java
// Java implementation for the above approachimport java.util.Arrays;class GFG { // Function to find minimum sum absolute // difference from two arrays public static int minAbsoluteDiffSum(int a[], int b[], int n) { // Variable to store the // initial absolute difference sum int sum = 0; // Make another vector to // store the elements of a in // sorted order int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = a[i]; sum += Math.abs(a[i] - b[i]); } // Variable to store the minimum sum int min_answer = sum; // Sort the copy array of a Arrays.sort(nums); for (int i = 0; i < n; i++) { // Binary Search for elements // just greater than b[i]. int it = lower_bound(nums, 0, nums.length, b[i]); // Take minimum from just // greater and less than b[i]. int cur = Math.min(Math.abs(nums[(Math.min(it, (n - 1)))] - b[i]), Math.abs(nums[(Math.max(0, it - 1))] - b[i])); // update the minimum answer if (cur < Math.abs(a[i] - b[i])) { min_answer = Math.min(min_answer, sum - Math.abs(a[i] - b[i]) + cur); } } return min_answer; } public static int lower_bound(int[] a, int low, int high, int e) { if (low < 0) return 0; if (low >= high) { if (e <= a[low]) return low; return low + 1; } int mid = (int)Math.floor((low + high) / 2); if (e > a[mid]) return lower_bound(a, mid + 1, high, e); return lower_bound(a, low, mid, e); } // Driver Code public static void main(String args[]) { int a[] = { 1, 9, 4, 2 }; int b[] = { 2, 3, 7, 1 }; int N = a.length; System.out.println(minAbsoluteDiffSum(a, b, N)); }}// This code is contributed by saurabh_jaiswal. |
Python3
# python implementation for the above approachfrom bisect import bisect_left# Function to find minimum sum absolute# difference from two arraysdef minAbsoluteDiffSum(a, b, n): # Variable to store the # initial absolute difference sum sum = 0 # Make another vector to # store the elements of a in # sorted order nums = [0 for _ in range(n)] for i in range(0, n): nums[i] = a[i] sum += abs(a[i] - b[i]) # Variable to store the minimum sum min_answer = sum # Sort the copy array of a nums.sort() for i in range(0, n): # Binary Search for elements # just greater than b[i]. it = bisect_left(nums, b[i], 0, len(nums)) # Take minimum from just # greater and less than b[i]. cur = min( abs(nums[min(it, (n - 1))] - b[i]), abs(nums[max(0, it - 1)] - b[i])) # update the minimum answer if (cur < abs(a[i] - b[i])): min_answer = min( min_answer, sum - abs(a[i] - b[i]) + cur) return min_answer# Driver Codeif __name__ == "__main__": a = [1, 9, 4, 2] b = [2, 3, 7, 1] N = len(a) print(minAbsoluteDiffSum(a, b, N))# This code is contributed by rakeshsahni |
C#
// C# implementation for the above approachusing System;class GFG { // Function to find minimum sum absolute // difference from two arrays public static int minAbsoluteDiffSum(int[] a, int[] b, int n) { // Variable to store the // initial absolute difference sum int sum = 0; // Make another vector to // store the elements of a in // sorted order int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = a[i]; sum += Math.Abs(a[i] - b[i]); } // Variable to store the minimum sum int min_answer = sum; // Sort the copy array of a Array.Sort(nums); for (int i = 0; i < n; i++) { // Binary Search for elements // just greater than b[i]. int it = lower_bound(nums, 0, nums.Length, b[i]); // Take minimum from just // greater and less than b[i]. int cur = Math.Min(Math.Abs(nums[(Math.Min(it, (n - 1)))] - b[i]), Math.Abs(nums[(Math.Max(0, it - 1))] - b[i])); // update the minimum answer if (cur < Math.Abs(a[i] - b[i])) { min_answer = Math.Min(min_answer, sum - Math.Abs(a[i] - b[i]) + cur); } } return min_answer; } public static int lower_bound(int[] a, int low, int high, int e) { if (low < 0) return 0; if (low >= high) { if (e <= a[low]) return low; return low + 1; } int mid = (int)((low + high) / 2); if (e > a[mid]) return lower_bound(a, mid + 1, high, e); return lower_bound(a, low, mid, e); } // Driver Code public static void Main() { int[] a = { 1, 9, 4, 2 }; int[] b = { 2, 3, 7, 1 }; int N = a.Length; Console.Write(minAbsoluteDiffSum(a, b, N)); }}// This code is contributed by saurabh_jaiswal. |
Javascript
<script> // JavaScript Program to implement // the above approach function lower_bound(a, low, high, e) { if (low < 0) return 0; if (low >= high) { if (e <= a[low]) return low; return low + 1; } let mid = Math.floor((low + high) / 2); if (e > a[mid]) return lower_bound(a, mid + 1, high, e); return lower_bound(a, low, mid, e); } // Function to find minimum sum absolute // difference from two arrays function minAbsoluteDiffSum(a, b, n) { // Variable to store the // initial absolute difference sum let sum = 0; // Make another vector to // store the elements of a in // sorted order let nums = new Array(n); for (let i = 0; i < n; i++) { nums[i] = a[i]; sum += Math.abs(a[i] - b[i]); } // Variable to store the minimum sum let min_answer = sum; // Sort the copy array of a nums.sort() for (let i = 0; i < n; i++) { // Binary Search for elements // just greater than b[i]. let it = lower_bound(nums, 0, nums.length, b[i]) // Take minimum from just // greater and less than b[i]. let cur = Math.min( Math.abs(nums[(Math.min(it, (n - 1)))] - b[i]), Math.abs(nums[(Math.max(0, it - 1))] - b[i])); // update the minimum answer if (cur < Math.abs(a[i] - b[i])) { min_answer = Math.min( min_answer, sum - Math.abs(a[i] - b[i]) + cur); } } return min_answer; } // Driver Code let a = [1, 9, 4, 2]; let b = [2, 3, 7, 1]; let N = a.length document.write(minAbsoluteDiffSum(a, b, N)); // This code is contributed by Potta Lokesh </script> |
Output:
6
Time Complexity: O(N log N), The loop that creates a copy of array a and computes the initial absolute difference sum runs in O(N) time.The sorting operation on the copy array of a takes O(N log N) time.The loop that performs the binary search and updates the minimum sum runs in O(N log N) time because it contains a binary search operation which takes O(log N) time in the worst case, and it is performed n times.Therefore, the overall time complexity of this implementation is O(N log N).
Auxiliary Space: O(N), The space used by the copy array of a is O(N) because it has n elements.The space used by the vector to store the sorted copy array of a is also O(N).Therefore, the overall space complexity of this implementation is O(N).
