Maximize the minimum value of Array by performing given operations at most K times
Given array A[] of size N and integer K, the task for this problem is to maximize the minimum value of the array by performing given operations at most K times. In one operation choose any index and increase that array element by 1.
Examples:
Input: A[] = {3, 1, 2, 4, 6, 2, 5}, K = 8
Output: 4
Explanation:
- Choose i = 1 and increase the element by 1 now A[] becomes {4, 1, 2, 4, 6, 2, 5}
- Choose i = 2 and increase the element by 1 now A[] becomes {4, 2, 2, 4, 6, 2, 5}
- Choose i = 2 and increase the element by 1 now A[] becomes {4, 3, 2, 4, 6, 2, 5}
- Choose i = 2 and increase the element by 1 now A[] becomes {4, 4, 2, 4, 6, 2, 5}
- Choose i = 3 and increase the element by 1 now A[] becomes {4, 4, 3, 4, 6, 2, 5}
- Choose i = 3 and increase the element by 1 now A[] becomes {4, 4, 4, 4, 6, 2, 5}
- Choose i = 6 and increase the element by 1 now A[] becomes {4, 4, 4, 4, 6, 3, 5}
- Choose i = 6 and increase the element by 1 now A[] becomes {4, 4, 4, 4, 6, 4, 5}
After all K = 8 operations minimum value of the array is 4.
Input: A[] = {1, 1, 1}, K = 10
Output: 4
Explanation:
- Choose i = 1 and increase the element by 1 now A[] becomes {2, 1, 1}
- Choose i = 1 and increase the element by 1 now A[] becomes {3, 1, 1}
- Choose i = 1 and increase the element by 1 now A[] becomes {4, 1, 1}
- Choose i = 2 and increase the element by 1 now A[] becomes {4, 2, 1}
- Choose i = 2 and increase the element by 1 now A[] becomes {4, 3, 1}
- Choose i = 2 and increase the element by 1 now A[] becomes {4, 4, 1}
- Choose i = 3 and increase the element by 1 now A[] becomes {4, 4, 2}
- Choose i = 3 and increase the element by 1 now A[] becomes {4, 4, 3}
- Choose i = 3 and increase the element by 1 now A[] becomes {4, 4, 4}
- Choose i = 3 and increase the element by 1 now A[] becomes {4, 4, 5}
After all K = 10 operations minimum value of array is 4
Naïve Approach: The basic way to solve the problem is as follows:
Check For every value from 1 to 109 is possible or not. This can be done for each value it is possible to make every element at least equal to greater than number that we are checking for.
Time Complexity: O(N2)
Auxiliary Space: O(1)
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 109. f(N) is monotonic function represents whether every element of array can be made at least N by at most K operations. it is of the form TTTTTTFFFFFFF. we have to find when the last time function was true using Binary Search.
Below are the steps for the above approach:
- Set the low and high ranges of binary search.
- isPossible(mid) function used to check whether every element of array A[] can be made at least mid by performing given operations at most K number of times.
- Run while loop till high and low are not equal.
- In the while loop find the middle element and store it in a mid variable.
- Check if every array element of array A[] can be made at least mid in at most K operations using the isPossible() function. If it is true, set low = mid else high = mid – 1.
- After the loop ends if isPossible() is possibly true for high then return high else return low.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; #define int long long // Function to check if it is possible to // make each element at least mid by // K number of operations bool isPossible( int mid, int A[], int N, int K) { // Number of operations required to make // every element of array atleast mid int reqOperations = 0; // iterating to turn each array element // into atleast mid for ( int i = 0; i < N; i++) { // current element is less than required // element if (A[i] < mid) reqOperations += (mid - A[i]); } // if number of required operations are less // than number of operations available then // return true else false; return reqOperations <= K; } // Function to maximize the minimum element // of array by performing given operations // at most K times int maximizeMinimumElement( int A[], int N, int K) { // Range of binary search int low = 1, high = 3000000000; // 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 (isPossible(mid, A, N, K)) { low = mid; } else { high = mid - 1; } } // Checking whether high can be answer if (isPossible(high, A, N, K)) return high; // If not then it is low else return low; } // Driver Code int32_t main() { // Input 1 int K = 8; int A[] = { 3, 1, 2, 4, 6, 2, 5 }, N = 7; // Function Call cout << maximizeMinimumElement(A, N, K) << endl; return 0; } |
Java
// Java code for the above approach class GFG { // Function to check if it is possible to // make each element at least mid by K number of // operations static boolean IsPossible( long mid, int [] A, int N, int K) { long reqOperations = 0 ; // Iterating to turn each array element into at // least mid for ( int i = 0 ; i < N; i++) { // If current element is less than required // element if (A[i] < mid) reqOperations += (mid - A[i]); } // If the number of required operations are less // than or equal to the number of operations // available return reqOperations <= K; } static long MaximizeMinimumElement( int [] A, int N, int K) { // Range of binary search long low = 1 , high = 3000000000L; // Running loop until high is // not equal to low while (high - low > 1 ) { // mid is the average of low and high long mid = (low + high) / 2 ; // Checking the test function if (IsPossible(mid, A, N, K)) { low = mid; } else { high = mid - 1 ; } } // Checking whether high can be the answer if (IsPossible(high, A, N, K)) return high; else return low; } // Driver Code public static void main(String[] args) { // Input 1 int K = 8 ; int [] A = { 3 , 1 , 2 , 4 , 6 , 2 , 5 }; int N = 7 ; // Function Call System.out.println(MaximizeMinimumElement(A, N, K)); } } // This code is contributed by ragul21 |
Python3
def isPossible(mid, A, N, K): reqOperations = 0 for i in range (N): if A[i] < mid: reqOperations + = (mid - A[i]) return reqOperations < = K def maximizeMinimumElement(A, N, K): low = 1 high = 3000000000 while high - low > 1 : mid = (low + high) / / 2 if isPossible(mid, A, N, K): low = mid else : high = mid - 1 #Checking whether high can be answer if isPossible(high, A, N, K): return high else : return low # Input 1 K = 8 A = [ 3 , 1 , 2 , 4 , 6 , 2 , 5 ] N = len (A) # Function Call print (maximizeMinimumElement(A, N, K)) |
C#
using System; class GFG { // Function to check if it is possible to // make each element at least mid by K number of operations static bool IsPossible( long mid, int [] A, int N, int K) { long reqOperations = 0; // Iterating to turn each array element into at least mid for ( int i = 0; i < N; i++) { // If current element is less than required element if (A[i] < mid) reqOperations += (mid - A[i]); } // If the number of required operations are less // than or equal to the number of operations available return reqOperations <= K; } static long MaximizeMinimumElement( int [] A, int N, int K) { // Range of binary search long low = 1, high = 3000000000; // Running loop until high is // not equal to low while (high - low > 1) { // mid is the average of low and high long mid = (low + high) / 2; // Checking the test function if (IsPossible(mid, A, N, K)) { low = mid; } else { high = mid - 1; } } // Checking whether high can be the answer if (IsPossible(high, A, N, K)) return high; else return low; } // Driver Code static void Main() { // Input 1 int K = 8; int [] A = { 3, 1, 2, 4, 6, 2, 5 }; int N = 7; // Function Call Console.WriteLine(MaximizeMinimumElement(A, N, K)); } } |
Javascript
// JavaScript code to implement the approach // Function to check if it is possible to // make each element at least mid by K // number of operations function isPossible(mid, A, N, K) { // Number of operations required to // make every element of array at least mid let reqOperations = 0; // Iterating to turn each array element // into at least mid for (let i = 0; i < N; i++) { // If the current element is less // than the required element if (A[i] < mid) { reqOperations += (mid - A[i]); } } // If the number of required operations // are less than or equal to the number of // operations available, return true, else false return reqOperations <= K; } // Function to maximize the minimum element // of the array by performing given // operations at most K times function maximizeMinimumElement(A, N, K) { // Range of binary search let low = 1; let high = 3000000000; // Running a loop until high is not equal to low while (high - low > 1) { // Mid is the average of low and high let mid = Math.floor((low + high) / 2); // Checking the test function if (isPossible(mid, A, N, K)) { low = mid; } else { high = mid - 1; } } // Checking whether high can be the answer if (isPossible(high, A, N, K)) { return high; } // If not, then it is low return low; } // Driver Code // Input const K = 8; const A = [3, 1, 2, 4, 6, 2, 5]; const N = 7; // Function Call console.log(maximizeMinimumElement(A, N, K)); |
4
Time Complexity: O(N*log(10^9))
Auxiliary Space: O(1)
Contact Us