Minimize the maximum difference of adjacent elements after at most K insertions | Java program to find the minimum of maximum difference between adjacent elements after at most K insertions ; Calculate the maximum adjacent difference ; If the maximum adjacent difference is already zero ; best and worst specifies range of the maximum adjacent difference ; To store the no of insertions required for respective values of mid ; If the number of insertions required exceeds K ; Otherwise ; Driver code
import java . util . * ; class GFG { static int minMaxDiff ( int arr [ ] , int n , int k ) { int max_adj_dif = Integer . MIN_VALUE ; for ( int i = 0 ; i < n - 1 ; i ++ ) max_adj_dif = Math . max ( max_adj_dif , Math . abs ( arr [ i ] - arr [ i + 1 ] ) ) ; if ( max_adj_dif == 0 ) return 0 ; int best = 1 ; int worst = max_adj_dif ; int mid , required ; while ( best < worst ) { mid = ( best + worst ) / 2 ; required = 0 ; for ( int i = 0 ; i < n - 1 ; i ++ ) { required += ( Math . abs ( arr [ i ] - arr [ i + 1 ] ) - 1 ) / mid ; } if ( required > k ) best = mid + 1 ; else worst = mid ; } return worst ; } public 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 ) ) ; } }