Minimize the maximum value of the absolute difference
Given array A[] of size N (1 <= N <= 105). The following operation should be performed until array A[] is not empty. choose three integers X, Y, and Z, Take out an element from array A[] (1 <= A[i] <= 109), and choose one integer out of the chosen three integers X, Y, and Z record absolute difference between them, then delete the element. The task for this problem is to minimize the maximum value of this absolute difference.
Examples:
Input: A[] = {1, 7, 7, 9, 9, 9}
Output: 0
Explanation: If X = 1, Y = 7 and Z = 9
- for A[1] = 1 choose X = 1 the absolute difference is 0
- for A[2] = 7 choose Y = 7 the absolute difference is 0
- for A[3] = 7 choose Y = 7 the absolute difference is 0
- for A[4] = 9 choose Z = 9 the absolute difference is 0
- for A[5] = 9 choose Z = 9 the absolute difference is 0
- for A[6] = 9 choose Z = 9 the absolute difference is 0
the maximum absolute difference is 0
Input: A[] = {5, 4, 2, 1, 30, 60}
Output: 2
Explanation: If X = 3, Y = 30 and Z = 60
- for A[1] = 5 choose X = 3 the absolute difference is 2
- for A[2] = 4 choose X = 3 the absolute difference is 1
- for A[3] = 2 choose X = 3 the absolute difference is 1
- for A[4] = 1 choose X = 3 the absolute difference is 2
- for A[5] = 30 choose Y = 30 the absolute difference is 0
- for A[6] = 60 choose Z = 60 the absolute difference is 0
maximum absolute difference is 2
Efficient Approach: To solve the problem follow the below idea:
Binary Search can be used to solve this problem and the range of binary search will be 1 to maxArrayElement(A[]) is monotonic function represents whether absolute difference of mid can be achieved or not. it is of the form FFFFFFFTTTTTTT. we have to find when the first time function becomes true using Binary Search.
Below are the steps for the above approach:
- Set low and high range of binary serach.
- ispos(mid) function used to check whether mid can be the maximum absolute difference.
- Run while loop till high and low are not equal.
- In while loop find middle element and store it in mid variable.
- Check if that mid can be maximum value of array using ispos() function. If it is true then set high = mid else low = mid + 1.
- After loop ends if ispos() true for low then return low else return high.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to check given absolute difference // is possible or not bool ispos( int mid, int A[], int N) { // declaring array containing X vector< int > sze{ A[0] + mid }; // Iterating over N elements starting // from first index for ( int i = 1; i < N; i++) { // Declaring answer variable for tracking int ans = INT_MAX; // Iterating on chosen elements for ( int j = 0; j < sze.size(); j++) { ans = min(ans, abs (A[i] - sze[j])); } // if answer is greater than mid if (ans > mid) { // Return false if elements required to // have maximum absolute difference mid // is greater than 3 if (sze.size() == 3) return false ; // push A[i] + mid to our array sze.push_back(A[i] + mid); } } // Return true if it is possible return true ; } // Function to find Minimize the // maximum value of absolute difference int minimizeMaximumAbsDiff( int A[], int N) { // sort the array sort(A, A + N); // Range of binary search int low = 0, high = A[N - 1]; // Running loop till high // is not equal to low while (high - low > 1) { // mid is average of low and high int mid = (low + high) / 2; // Checking test function if (ispos(mid, A, N)) { high = mid; } else { low = mid + 1; } } // Checking whether low can be answer if (ispos(low, A, N)) return low; // If not then it is high else return high; } // Driver Code int32_t main() { // Input 1 int N = 6, A[] = { 1, 7, 7, 9, 9, 9 }; // Function Call cout << minimizeMaximumAbsDiff(A, N) << endl; // Input 2 int N1 = 6, A1[] = { 5, 4, 2, 1, 30, 60 }; // Function Call cout << minimizeMaximumAbsDiff(A1, N1) << endl; return 0; } |
Java
import java.util.Arrays; public class GFG { // Function to check given absolute difference // is possible or not static boolean isPos( int mid, int [] A, int N) { // declaring array containing X int [] sze = new int []{A[ 0 ] + mid}; // Iterating over N elements starting // from first index for ( int i = 1 ; i < N; i++) { // Declaring answer variable for tracking int ans = Integer.MAX_VALUE; // Iterating on chosen elements for ( int j = 0 ; j < sze.length; j++) { ans = Math.min(ans, Math.abs(A[i] - sze[j])); } // if answer is greater than mid if (ans > mid) { // Return false if elements required to // have maximum absolute difference mid // is greater than 3 if (sze.length == 3 ) return false ; // push A[i] + mid to our array sze = Arrays.copyOf(sze, sze.length + 1 ); sze[sze.length - 1 ] = A[i] + mid; } } // Return true if it is possible return true ; } // Function to find Minimize the // maximum value of absolute difference static int minimizeMaximumAbsDiff( int [] A, int N) { // sort the array Arrays.sort(A); // Range of binary search int low = 0 , high = A[N - 1 ]; // Running loop till high // is not equal to low while (high - low > 1 ) { // mid is average of low and high int mid = (low + high) / 2 ; // Checking test function if (isPos(mid, A, N)) { high = mid; } else { low = mid + 1 ; } } // Checking whether low can be answer if (isPos(low, A, N)) return low; // If not then it is high else return high; } // Driver Code public static void main(String[] args) { // Input 1 int N = 6 ; int [] A = { 1 , 7 , 7 , 9 , 9 , 9 }; // Function Call System.out.println(minimizeMaximumAbsDiff(A, N)); // Input 2 int N1 = 6 ; int [] A1 = { 5 , 4 , 2 , 1 , 30 , 60 }; // Function Call System.out.println(minimizeMaximumAbsDiff(A1, N1)); } } // This code is contributed by rohit singh |
Python
# Function to check if given absolute difference # is possible or not def ispos(mid, A, N): # declaring array containing X sze = [A[ 0 ] + mid] # Iterating over N elements starting # from the first index for i in range ( 1 , N): # Declaring answer variable for tracking ans = float ( 'inf' ) # Iterating on chosen elements for j in range ( len (sze)): ans = min (ans, abs (A[i] - sze[j])) # if answer is greater than mid if ans > mid: # Return false if elements required to # have the maximum absolute difference mid # is greater than 3 if len (sze) = = 3 : return False # push A[i] + mid to our array sze.append(A[i] + mid) # Return true if it is possible return True # Function to minimize the maximum value of absolute difference def minimizeMaximumAbsDiff(A, N): # sort the array A.sort() # Range of binary search low, high = 0 , A[N - 1 ] # Running loop until high # is not equal to low while high - low > 1 : # mid is average of low and high mid = (low + high) / / 2 # Checking test function if ispos(mid, A, N): high = mid else : low = mid + 1 # Checking whether low can be the answer if ispos(low, A, N): return low # If not then it is high else : return high # Driver Code # Input 1 N = 6 A = [ 1 , 7 , 7 , 9 , 9 , 9 ] # Function Call print (minimizeMaximumAbsDiff(A, N)) # Input 2 N1 = 6 A1 = [ 5 , 4 , 2 , 1 , 30 , 60 ] # Function Call print (minimizeMaximumAbsDiff(A1, N1)) |
C#
using System; public class GFG { // Function to check if given absolute difference // is possible or not static bool IsPos( int mid, int [] A, int N) { // declaring array containing X int [] sze = new int [] { A[0] + mid }; // Iterating over N elements starting // from the first index for ( int i = 1; i < N; i++) { // Declaring answer variable for tracking int ans = int .MaxValue; // Iterating on chosen elements for ( int j = 0; j < sze.Length; j++) { ans = Math.Min(ans, Math.Abs(A[i] - sze[j])); } // if answer is greater than mid if (ans > mid) { // Return false if elements required to // have maximum absolute difference mid // is greater than 3 if (sze.Length == 3) return false ; // push A[i] + mid to our array Array.Resize( ref sze, sze.Length + 1); sze[sze.Length - 1] = A[i] + mid; } } // Return true if it is possible return true ; } // Function to find Minimize the // maximum value of absolute difference static int MinimizeMaximumAbsDiff( int [] A, int N) { // sort the array Array.Sort(A); // Range of binary search int low = 0, high = A[N - 1]; // Running loop until high // is not equal to low while (high - low > 1) { // mid is the average of low and high int mid = (low + high) / 2; // Checking test function if (IsPos(mid, A, N)) { high = mid; } else { low = mid + 1; } } // Checking whether low can be the answer if (IsPos(low, A, N)) return low; // If not, then it is high else return high; } // Driver Code public static void Main( string [] args) { // Input 1 int N = 6; int [] A = { 1, 7, 7, 9, 9, 9 }; // Function Call Console.WriteLine(MinimizeMaximumAbsDiff(A, N)); // Input 2 int N1 = 6; int [] A1 = { 5, 4, 2, 1, 30, 60 }; // Function Call Console.WriteLine(MinimizeMaximumAbsDiff(A1, N1)); } } |
Javascript
// Function to check if the given // absolute difference is possible or not function ispos(mid, A, N) { let sze = [A[0] + mid]; for (let i = 1; i < N; i++) { let ans = Number.MAX_SAFE_INTEGER; for (let j = 0; j < sze.length; j++) { ans = Math.min(ans, Math.abs(A[i] - sze[j])); } if (ans > mid) { if (sze.length === 3) { return false ; } sze.push(A[i] + mid); } } return true ; } // Function to find Minimize the // maximum value of absolute difference function minimizeMaximumAbsDiff(A, N) { A.sort((a, b) => a - b); let low = 0, high = A[N - 1]; while (high - low > 1) { let mid = Math.floor((low + high) / 2); if (ispos(mid, A, N)) { high = mid; } else { low = mid + 1; } } if (ispos(low, A, N)) { return low; } else { return high; } } // Driver Code // Input 1 let N = 6, A = [1, 7, 7, 9, 9, 9]; console.log(minimizeMaximumAbsDiff(A, N)); // Input 2 let N1 = 6, A1 = [5, 4, 2, 1, 30, 60]; console.log(minimizeMaximumAbsDiff(A1, N1)); |
0 2
Time Complexity: O(N*logN)
Auxiliary Space: O(1)
Contact Us