Minimize maximum array element possible by at most K splits on the given array | C ++ program for the above approach ; Function to check if all array elements can be reduced to at most mid by at most K splits ; Stores the number of splits required ; Traverse the array arr [ ] ; Update count ; If possible , return true . Otherwise return false ; Function to find the minimum possible value of maximum array element that can be obtained by at most K splits ; Set lower and upper limits ; Perform Binary Search ; Calculate mid ; Check if all array elements can be reduced to at most mid value by at most K splits ; Update the value of hi ; Otherwise ; Update the value of lo ; Return the minimized maximum element in the array ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int possible ( int A [ ] , int N , int mid , int K ) { int count = 0 ; for ( int i = 0 ; i < N ; i ++ ) { count += ( A [ i ] - 1 ) / mid ; } return count <= K ; } int minimumMaximum ( int A [ ] , int N , int K ) { int lo = 1 ; int hi = * max_element ( A , A + N ) ; int mid ; while ( lo < hi ) { mid = ( lo + hi ) / 2 ; if ( possible ( A , N , mid , K ) ) { hi = mid ; } else { lo = mid + 1 ; } } return hi ; } int main ( ) { int arr [ ] = { 2 , 4 , 8 , 2 } ; int K = 4 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << minimumMaximum ( arr , N , K ) ; return 0 ; }