Given three arrays a[], b[] and c[] of sizes A, B and C respectively, the task is to find the minimum possible value of abs(a[i] – b[j]) + abs(b[j] – c[k]) where 0 ? i ? A, 0 ? j ? B and 0 ? k ? C.
Examples:
Input: A = 3, B = 2, C = 2, a[] = {1, 8, 5}, b[] = {2, 9}, c[] = {5, 4}
Output: 3
Explanation:
The triplet (a[0], b[0], c[1]), i.e. (1, 2, 4) has minimum sum of absolute difference of pairs, i.e. abs(1 – 2) + abs(2 – 4) = 1 + 2 = 3.Input: A = 4, B = 3, C = 3, a[] = {4, 5, 1, 7}, b[] = {8, 5, 6}, c[] = {2, 7, 12}
Output: 2
Explanation:
The triplet (a[1], b[1], c[1]), i.e. (1, 5, 7) has minimum sum of absolute difference of pairs, i.e. abs(5 – 5) + abs(5 – 7) = 0 + 2 = 2.
Approach: The idea to solve this problem is to sort the arrays a[] and c[] and then traverse the array b[] and find the elements which satisfy the given condition.
Follow the steps below to solve the problem:
- Initialize the variable, say min, as INT_MAX, to store the minimum possible value.
- Sort the arrays a[] and c[] in increasing order.
- Traverse the array b[] and for each element, say b[i], find the closest element to b[i] from the arrays a[] and c[] as arr_close and crr_close and do the following:
- To find the closest element, firstly find the lower_bound of the target element b[i].
- If the lower bound is found, check if it is the first element of the array or not. If it is not, then compare the lower bound and its previous element with the target element and find which is closest to the target element.
- If the lower bound is not found, then the closest element will be the last element of the array.
- Update min as the minimum of abs(b[i] – arr_close) + abs(b[i] – crr_close).
- After completing the above steps, print the value of min as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to find the value // closest to K in the array A[] int closestValue(vector<int> A, int k) { // Initialize close value as the // end element int close = A.back(); // Find lower bound of the array auto it = lower_bound(A.begin(), A.end(), k); // If lower_bound is found if (it != A.end()) { close = *it; // If lower_bound is not // the first array element if (it != A.begin()) { // If *(it - 1) is closer to k if ((k - *(it - 1)) < (close - k)) { close = *(it - 1); } } } // Return closest value of k return close; } // Function to find the minimum sum of // abs(arr[i] - brr[j]) and abs(brr[j]-crr[k]) void minPossible(vector<int> arr, vector<int> brr, vector<int> crr) { // Sort the vectors arr and crr sort(arr.begin(), arr.end()); sort(crr.begin(), crr.end()); // Initialize minimum as INT_MAX int minimum = INT_MAX; // Traverse the array brr[] for (int val : brr) { // Stores the element closest // to val from the array arr[] int arr_close = closestValue(arr, val); // Stores the element closest // to val from the array crr[] int crr_close = closestValue(crr, val); // If sum of differences is minimum if (abs(val - arr_close) + abs(val - crr_close) < minimum) // Update the minimum minimum = abs(val - arr_close) + abs(val - crr_close); } // Print the minimum absolute // difference possible cout << minimum; } // Driver Code int main() { vector<int> a = { 1, 8, 5 }; vector<int> b = { 2, 9 }; vector<int> c = { 5, 4 }; // Function Call minPossible(a, b, c); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Lower_bound function public static int lower_bound(int arr[], int key) { int low = 0; int high = arr.length - 1; while (low < high) { int mid = low + (high - low) / 2; if (arr[mid] >= key) { high = mid; } else { low = mid + 1; } } return low; } // Function to find the value // closest to K in the array A[] static int closestValue(int A[], int k) { // Initialize close value as the // end element int close = A[A.length - 1]; // Find lower bound of the array int it = lower_bound(A, k); // If lower_bound is found if (it != A.length) { close = A[it]; // If lower_bound is not // the first array element if (it != 0) { // If *(it - 1) is closer to k if ((k - A[it - 1]) < (close - k)) { close = A[it - 1]; } } } // Return closest value of k return close; } // Function to find the minimum sum of // abs(arr[i] - brr[j]) and abs(brr[j]-crr[k]) static void minPossible(int arr[], int brr[], int crr[]) { // Sort the vectors arr and crr Arrays.sort(arr); Arrays.sort(crr); // Initialize minimum as INT_MAX int minimum = Integer.MAX_VALUE; // Traverse the array brr[] for(int val : brr) { // Stores the element closest // to val from the array arr[] int arr_close = closestValue(arr, val); // Stores the element closest // to val from the array crr[] int crr_close = closestValue(crr, val); // If sum of differences is minimum if (Math.abs(val - arr_close) + Math.abs(val - crr_close) < minimum) // Update the minimum minimum = Math.abs(val - arr_close) + Math.abs(val - crr_close); } // Print the minimum absolute // difference possible System.out.println(minimum); } // Driver Code public static void main(String[] args) { int a[] = { 1, 8, 5 }; int b[] = { 2, 9 }; int c[] = { 5, 4 }; // Function Call minPossible(a, b, c); } } // This code is contributed by Kingash |
Python3
# Python program to implement # the above approach # Lower_bound function def lower_bound(arr, key): low = 0; high = len(arr) - 1; while (low < high): mid = low + (high - low) // 2; if (arr[mid] >= key): high = mid; else: low = mid + 1; return low; # Function to find the value # closest to K in the array A[] def closestValue(A, k): # Initialize close value as the # end element close = A[-1]; # Find lower bound of the array it = lower_bound(A, k); # If lower_bound is found if (it != len(A)): close = A[it]; # If lower_bound is not # the first array element if (it != 0): # If *(it - 1) is closer to k if ((k - A[it - 1]) < (close - k)): close = A[it - 1]; # Return closest value of k return close; # Function to find the minimum sum of # abs(arr[i] - brr[j]) and abs(brr[j]-crr[k]) def minPossible(arr, brr, crr): # Sort the vectors arr and crr arr.sort(); crr.sort(); # Initialize minimum as LET_MAX minimum = 10**9; # Traverse the array brr[] for val in brr: # Stores the element closest # to val from the array arr[] arr_close = closestValue(arr, val); # Stores the element closest # to val from the array crr[] crr_close = closestValue(crr, val); # If sum of differences is minimum if (abs(val - arr_close) + abs(val - crr_close) < minimum): # Update the minimum minimum = abs(val - arr_close) + abs(val - crr_close); # Print the minimum absolute # difference possible print(minimum); # Driver code a = [ 1, 8, 5 ]; b = [ 2, 9 ]; c = [ 5, 4 ]; # Function Call minPossible(a, b, c); # This code is contributed by gfgking |
C#
// C# program for the above approach using System; class GFG{ // Lower_bound function public static int lower_bound(int[] arr, int key) { int low = 0; int high = arr.Length - 1; while (low < high) { int mid = low + (high - low) / 2; if (arr[mid] >= key) { high = mid; } else { low = mid + 1; } } return low; } // Function to find the value // closest to K in the array A[] static int closestValue(int []A, int k) { // Initialize close value as the // end element int close = A[A.Length - 1]; // Find lower bound of the array int it = lower_bound(A, k); // If lower_bound is found if (it != A.Length) { close = A[it]; // If lower_bound is not // the first array element if (it != 0) { // If *(it - 1) is closer to k if ((k - A[it - 1]) < (close - k)) { close = A[it - 1]; } } } // Return closest value of k return close; } // Function to find the minimum sum of // abs(arr[i] - brr[j]) and abs(brr[j]-crr[k]) static void minPossible(int[] arr, int[] brr, int[] crr) { // Sort the vectors arr and crr Array.Sort(arr); Array.Sort(crr); // Initialize minimum as INT_MAX int minimum = Int32.MaxValue; // Traverse the array brr[] foreach(int val in brr) { // Stores the element closest // to val from the array arr[] int arr_close = closestValue(arr, val); // Stores the element closest // to val from the array crr[] int crr_close = closestValue(crr, val); // If sum of differences is minimum if (Math.Abs(val - arr_close) + Math.Abs(val - crr_close) < minimum) // Update the minimum minimum = Math.Abs(val - arr_close) + Math.Abs(val - crr_close); } // Print the minimum absolute // difference possible Console.WriteLine(minimum); } // Driver Code static void Main() { int []a = { 1, 8, 5 }; int []b = { 2, 9 }; int []c = { 5, 4 }; // Function Call minPossible(a, b, c); } } // This code is contributed by SoumikMondal |
Javascript
<script> // JavaScript program to implement // the above approach // Lower_bound function function lower_bound(arr, key) { let low = 0; let high = arr.length - 1; while (low < high) { let mid = low + Math.floor((high - low) / 2); if (arr[mid] >= key) { high = mid; } else { low = mid + 1; } } return low; } // Function to find the value // closest to K in the array A[] function closestValue(A, k) { // Initialize close value as the // end element let close = A[A.length - 1]; // Find lower bound of the array let it = lower_bound(A, k); // If lower_bound is found if (it != A.length) { close = A[it]; // If lower_bound is not // the first array element if (it != 0) { // If *(it - 1) is closer to k if ((k - A[it - 1]) < (close - k)) { close = A[it - 1]; } } } // Return closest value of k return close; } // Function to find the minimum sum of // abs(arr[i] - brr[j]) and abs(brr[j]-crr[k]) function minPossible(arr, brr, crr) { // Sort the vectors arr and crr arr.sort(); crr.sort(); // Initialize minimum as LET_MAX let minimum = Number.MAX_VALUE; // Traverse the array brr[] for(let val in brr) { // Stores the element closest // to val from the array arr[] let arr_close = closestValue(arr, val); // Stores the element closest // to val from the array crr[] let crr_close = closestValue(crr, val); // If sum of differences is minimum if (Math.abs(val - arr_close) + Math.abs(val - crr_close) < minimum) // Update the minimum minimum = Math.abs(val - arr_close) + Math.abs(val - crr_close); } // Print the minimum absolute // difference possible document.write(minimum); } // Driver code let a = [ 1, 8, 5 ]; let b = [ 2, 9 ]; let c = [ 5, 4 ]; // Function Call minPossible(a, b, c); // This code is contributed by susmitakundugoaldanga. </script> |
Output:
3
Time Complexity: O(A*log A + C*log C + B*log A + B*log C)
Auxiliary Space: O(A + B + C)
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!
