Given an array of N elements, the task is to minimize the maximum difference of adjacent elements by inserting at most K elements in the array.
Examples:
Input: arr = [2, 6, 8] K = 1
Output: 2
Explanation:
After insertion of 4 in between 2 and 6, the array becomes [2, 4, 6, 8]. In this case the maximum difference between any adjacent element is 2, which is the minimum that can be.
Input: arr = [3, 12] K = 2
Output: 3
Explanation:
After insertion of 6 and 9 in between 3 and 12, the array becomes [3, 6, 9, 12]. In this case the maximum difference between any adjacent element is 3, which is the minimum that can be.
Approach: In order to solve this problem, we are using the following Binary Search based approach:
- Find the maximum difference between any two adjacent element in the array and store it in a variable, say worst.
- Search from best(1 initially) to worst and for every mid value find the number of insertions required.
- Whenever the number of insertions is greater than K for a particular value of mid, search between [mid + 1, worst], that is the higher half. Otherwise search between [best, mid-1], that is the lower half to check if the maximum difference can be further minimized with at most K insertions.
- The final worst value after termination of the loop gives the answer.
Below code is the implementation of the above approach:
C++
// C++ Program to find the minimum of maximum// differerence between adjacent elements// after at most K insertions#include <bits/stdc++.h>using namespace std;int minMaxDiff(int arr[], int n, int k){ int max_adj_dif = INT_MIN; // Calculate the maximum // adjacent difference for (int i = 0; i < n - 1; i++) max_adj_dif = max(max_adj_dif, abs(arr[i] - arr[i + 1])); // If the maximum adjacent // difference is already zero if (max_adj_dif == 0) return 0; // best and worst specifies // range of the maximum // adjacent difference int best = 1; int worst = max_adj_dif; int mid, required; while (best < worst) { mid = (best + worst) / 2; // To store the no of insertions // required for respective // values of mid required = 0; for (int i = 0; i < n - 1; i++) { required += (abs(arr[i] - arr[i + 1]) - 1) / mid; } // If the number of insertions // required exceeds K if (required > k) best = mid + 1; // Otherwise else worst = mid; } return worst;}// Driver codeint main(){ int arr[] = { 3, 12, 25, 50 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 7; cout << minMaxDiff(arr, n, k); return 0;} |
Java
// Java program to find the minimum // of maximum difference between // adjacent elements after at most// K insertionsimport java.util.*;class GFG{ static int minMaxDiff(int arr[], int n, int k){ int max_adj_dif = Integer.MIN_VALUE; // Calculate the maximum // adjacent difference for(int i = 0; i < n - 1; i++) max_adj_dif = Math.max(max_adj_dif, Math.abs(arr[i] - arr[i + 1])); // If the maximum adjacent // difference is already zero if (max_adj_dif == 0) return 0; // best and worst specifies // range of the maximum // adjacent difference int best = 1; int worst = max_adj_dif; int mid, required; while (best < worst) { mid = (best + worst) / 2; // To store the no of insertions // required for respective // values of mid required = 0; for(int i = 0; i < n - 1; i++) { required += (Math.abs(arr[i] - arr[i + 1]) - 1) / mid; } // If the number of insertions // required exceeds K if (required > k) best = mid + 1; // Otherwise else worst = mid; } return worst;}// Driver codepublic static void main(String[] args){ int arr[] = { 3, 12, 25, 50 }; int n = arr.length; int k = 7; System.out.println(minMaxDiff(arr, n, k));}}// This code is contributed by ANKITKUMAR34 |
Python 3
# Python3 program to find the minimum # of maximum difference between # adjacent elements after at most# K insertionsdef minMaxDiff(arr, n, k): max_adj_dif = float('-inf'); # Calculate the maximum # adjacent difference for i in range(n - 1): max_adj_dif = max(max_adj_dif, abs(arr[i] - arr[i + 1])); # If the maximum adjacent # difference is already zero if (max_adj_dif == 0): return 0; # best and worst specifies # range of the maximum # adjacent difference best = 1; worst = max_adj_dif; while (best < worst): mid = (best + worst) // 2; # To store the no of insertions # required for respective # values of mid required = 0 for i in range(n - 1): required += (abs(arr[i] - arr[i + 1]) - 1) // mid # If the number of insertions # required exceeds K if (required > k): best = mid + 1; # Otherwise else: worst = mid return worst# Driver codearr = [ 3, 12, 25, 50 ]n = len(arr)k = 7print(minMaxDiff(arr, n, k))# This code is contributed by ANKITKUMAR34 |
C#
// C# program to find the minimum // of maximum difference between // adjacent elements after at most// K insertionsusing System;class GFG{ static int minMaxDiff(int []arr, int n, int k){ int max_adj_dif = int.MinValue; // Calculate the maximum // adjacent difference for(int i = 0; i < n - 1; i++) max_adj_dif = Math.Max(max_adj_dif, Math.Abs(arr[i] - arr[i + 1])); // If the maximum adjacent // difference is already zero if (max_adj_dif == 0) return 0; // best and worst specifies // range of the maximum // adjacent difference int best = 1; int worst = max_adj_dif; int mid, required; while (best < worst) { mid = (best + worst) / 2; // To store the no of insertions // required for respective // values of mid required = 0; for(int i = 0; i < n - 1; i++) { required += (Math.Abs(arr[i] - arr[i + 1]) - 1) / mid; } // If the number of insertions // required exceeds K if (required > k) best = mid + 1; // Otherwise else worst = mid; } return worst;}// Driver codepublic static void Main(String[] args){ int []arr = { 3, 12, 25, 50 }; int n = arr.Length; int k = 7; Console.WriteLine(minMaxDiff(arr, n, k));}}// This code is contributed by Princi Singh |
Javascript
<script>// javascript Program to find the minimum of maximum// differerence between adjacent elements// after at most K insertionsfunction minMaxDiff(arr, n, k){ var max_adj_dif = -1000000000; // Calculate the maximum // adjacent difference for (var i = 0; i < n - 1; i++) max_adj_dif = Math.max(max_adj_dif, Math.abs(arr[i] - arr[i + 1])); // If the maximum adjacent // difference is already zero if (max_adj_dif == 0) return 0; // best and worst specifies // range of the maximum // adjacent difference var best = 1; var worst = max_adj_dif; var mid, required; while (best < worst) { mid = (best + worst) / 2; // To store the no of insertions // required for respective // values of mid required = 0; for (var i = 0; i < n - 1; i++) { required += parseInt((Math.abs(arr[i] - arr[i + 1]) - 1) / mid); } // If the number of insertions // required exceeds K if (required > k) best = mid + 1; // Otherwise else worst = mid; } return worst;}// Driver codevar arr = [ 3, 12, 25, 50 ];var n = arr.length;var k = 7;document.write( minMaxDiff(arr, n, k));</script> |
Output:
5
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!