Minimize maximum array element possible by at most K splits on the given array
Given an array arr[] consisting of N positive integers and a positive integer K, the task is to minimize the maximum element present in the array by splitting at most K array elements into two numbers equal to their value.
Examples:
Input: arr[] = {2, 4, 8, 2}, K = 4
Output: 2
Explanation:
Following sequence of operations are required to be performed:
Operation 1: Splitting arr[1] (= 4) to {2, 2} modifies the array to {2, 2, 2, 8, 2}.
Operation 2: Splitting arr[3] (= 8) to {2, 6} modifies the array to {2, 2, 2, 2, 6, 2}.
Operation 3: Splitting arr[4] (= 6) to {2, 4} modifies the array to {2, 2, 2, 2, 2, 4, 2}.
Operation 4: Splitting arr[5] (= 4) to {2, 2} modifies the array to {2, 2, 2, 2, 2, 2, 2, 2}.
After completing the above operations, the maximum element present in the array is 2.Input: arr[] = {7, 17}, K = 2
Output: 7
Approach: The given problem can be solved based on the following observations:
- If X can be the maximum element in the array arr[] by performing at most K operations, then there exists some value K (K > X), which can also be the maximum element present in the array arr[] by performing at most K splitting of the array elements.
- If X can’t be the maximum element in the array A[] by performing at most K operations, then there exists some value K (K < X) which can also not be the maximum element in the array arr[] by performing at most K splits of array elements.
- Therefore, the idea is to use Binary Search for finding the value over the range [1, INT_MAX] which can be the possible maximum value after at most K splits.
Follow the steps below to solve the problem:
- Initialize two variables, say low and high as 1 and the maximum element in the array arr[] respectively.
- Iterate until low is less than high and perform the following steps:
- Find the middle value of the range [low, high] as mid = (low + high)/2.
- Initialize a variable, say count, to store the maximum number of splits of array elements required to make the maximum element equal to mid.
- Traverse the given array arr[] and update the value of count as (arr[i] – 1) / mid to count the number of splits required.
- If the value of count is at most K, then update the value of high as mid.
- Otherwise, update the value of low as (mid + 1).
- After completing the above steps, print the value of high as the resultant maximum element present in the array obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if all array // elements can be reduced to at // most mid by at most K splits int possible( int A[], int N, int mid, int K) { // Stores the number // of splits required int count = 0; // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Update count count += (A[i] - 1) / mid; } // If possible, return true. // Otherwise return false return count <= K; } // Function to find the minimum possible // value of maximum array element that // can be obtained by at most K splits int minimumMaximum( int A[], int N, int K) { // Set lower and upper limits int lo = 1; int hi = *max_element(A, A + N); int mid; // Perform Binary Search while (lo < hi) { // Calculate mid mid = (lo + hi) / 2; // Check if all array elements // can be reduced to at most // mid value by at most K splits if (possible(A, N, mid, K)) { // Update the value of hi hi = mid; } // Otherwise else { // Update the value of lo lo = mid + 1; } } // Return the minimized maximum // element in the array return hi; } // Driver Code 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; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check if all array // elements can be reduced to at // most mid by at most K splits static boolean possible( int A[], int N, int mid, int K) { // Stores the number // of splits required int count = 0 ; // Traverse the array arr[] for ( int i = 0 ; i < N; i++) { // Update count count += (A[i] - 1 ) / mid; } // If possible, return true. // Otherwise return false return count <= K; } // Function to find the minimum possible // value of maximum array element that // can be obtained by at most K splits static int minimumMaximum( int A[], int N, int K) { // Set lower and upper limits int lo = 1 ; Arrays.sort(A); int hi = A[N - 1 ]; int mid; // Perform Binary Search while (lo < hi) { // Calculate mid mid = (lo + hi) / 2 ; // Check if all array elements // can be reduced to at most // mid value by at most K splits if (possible(A, N, mid, K)) { // Update the value of hi hi = mid; } // Otherwise else { // Update the value of lo lo = mid + 1 ; } } // Return the minimized maximum // element in the array return hi; } // Driver Code public static void main (String[] args) { int arr[] = { 2 , 4 , 8 , 2 }; int K = 4 ; int N = arr.length; System.out.println(minimumMaximum(arr, N, K)); } } // This code is contributed by AnkThon |
Python3
# Python3 program for the above approach # Function to check if all array # elements can be reduced to at # most mid by at most K splits def possible(A, N, mid, K): # Stores the number # of splits required count = 0 # Traverse the array arr[] for i in range (N): # Update count count + = (A[i] - 1 ) / / mid # If possible, return true. # Otherwise return false return count < = K # Function to find the minimum possible # value of maximum array element that # can be obtained by at most K splits def minimumMaximum(A, N, K): # Set lower and upper limits lo = 1 hi = max (A) # Perform Binary Search while (lo < hi): # Calculate mid mid = (lo + hi) / / 2 # Check if all array elements # can be reduced to at most # mid value by at most K splits if (possible(A, N, mid, K)): # Update the value of hi hi = mid # Otherwise else : # Update the value of lo lo = mid + 1 # Return the minimized maximum # element in the array return hi # Driver Code if __name__ = = '__main__' : arr = [ 2 , 4 , 8 , 2 ] K = 4 N = len (arr) print (minimumMaximum(arr, N, K)) # This code is contributed by ipg2016107 |
C#
// C# program for the above approach using System; class GFG{ // Function to check if all array // elements can be reduced to at // most mid by at most K splits static bool possible( int [] A, int N, int mid, int K) { // Stores the number // of splits required int count = 0; // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Update count count += (A[i] - 1) / mid; } // If possible, return true. // Otherwise return false return count <= K; } // Function to find the minimum possible // value of maximum array element that // can be obtained by at most K splits static int minimumMaximum( int [] A, int N, int K) { // Set lower and upper limits int lo = 1; Array.Sort(A); int hi = A[N - 1]; int mid; // Perform Binary Search while (lo < hi) { // Calculate mid mid = (lo + hi) / 2; // Check if all array elements // can be reduced to at most // mid value by at most K splits if (possible(A, N, mid, K)) { // Update the value of hi hi = mid; } // Otherwise else { // Update the value of lo lo = mid + 1; } } // Return the minimized maximum // element in the array return hi; } // Driver Code public static void Main( string [] args) { int [] arr = { 2, 4, 8, 2 }; int K = 4; int N = arr.Length; Console.WriteLine(minimumMaximum(arr, N, K)); } } // This code is contributed by ukasp |
Javascript
<script> // javascript program for the above approach // Function to check if all array // elements can be reduced to at // most mid by at most K splits function possible(A, N, mid, K) { // Stores the number // of splits required var count = 0; var i; // Traverse the array arr[] for (i = 0; i < N; i++) { // Update count count += Math.floor((A[i] - 1) / mid); } // If possible, return true. // Otherwise return false if (count <= K) return true ; else return false } // Function to find the minimum possible // value of maximum array element that // can be obtained by at most K splits function minimumMaximum(A, N, K) { // Set lower and upper limits var lo = 1; var hi = Math.max.apply(Math,A); var mid; // Perform Binary Search while (lo < hi) { // Calculate mid mid = Math.floor((lo + hi) / 2); // Check if all array elements // can be reduced to at most // mid value by at most K splits if (possible(A, N, mid, K)) { // Update the value of hi hi = mid; } // Otherwise else { // Update the value of lo lo = mid + 1; } } // Return the minimized maximum // element in the array return hi; } // Driver Code var arr = [2, 4, 8, 2]; var K = 4; var N = arr.length; document.write(minimumMaximum(arr, N, K)); // This code is contributed by SURENDRA_GANGWAR. </script> |
2
Time Complexity: O(N * log M), where M is the maximum element of the array.
Auxiliary Space: O(1)