Maximize the smallest array element by incrementing all elements in a K-length subarray by 1 exactly M times
Given an array arr[] of size N, and integers M and K, the task is to find the maximum possible value of the smallest array element by performing M operations. In each operation, increase the value of all elements in a contiguous subarray of length K by 1.
Examples:
Input: arr[ ] = {2, 2, 2, 2, 1, 1}, M = 1, K = 3
Output: 2
Explanation: Update the last 3 elements on the first move then updated array is [2, 2, 2, 3, 2, 2]. The smallest element has a value of 2.Input: arr[ ] = {5, 8}, M = 5, K = 1
Output: 9
Approach: The problem can be solved by using Binary Search. Traverse the array arr[] and for every element arr[i], count the number of operations required. If the current element is required to be updated x times, then add x to the answer and update the consecutive segment of length K by x times.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; #define ll long long ll n, m, k, l, r, i; // Function to check if the smallest // value of v is achievable or not ll check(ll v, vector<ll>& a) { ll tec = 0, ans = 0; // Create array to // store previous moves vector<ll> b(n + k + 1); for (i = 0; i < n; i++) { // Remove previous moves tec -= b[i]; if (a[i] + tec < v) { // Add balance to ans ll mov = v - a[i] - tec; ans = ans + mov; // Update contiguous // subarray of length k tec += mov; b[i + k] = mov; } } // Number of moves // should not exceed m return (ans <= m); } // Function to find the maximum // value of the smallest array // element that can be obtained ll FindLargest(vector<ll> a) { l = 1; r = pow (10, 10); // Perform Binary search while (r - l > 0) { ll tm = (l + r + 1) / 2; if (check( tm , a)) l = tm ; else r = tm - 1; } return l; } // Driver Code int main() { // Given Input vector<ll> a{ 2, 2, 2, 2, 1, 1 }; m = 2; k = 3; n = a.size(); // Function Call cout << FindLargest(a); return 0; } |
Java
// Java program for above approach class GFG{ static long n, m, k, l, r, i; // Function to check if the smallest // value of v is achievable or not static boolean check( long v, long [] a) { long tec = 0 , ans = 0 ; // Create array to // store previous moves long [] b = new long [( int )(n + k + 1 )]; for ( int i = 0 ; i < n; i++) { // Remove previous moves tec -= b[i]; if (a[i] + tec < v) { // Add balance to ans long mov = v - a[i] - tec; ans = ans + mov; // Update contiguous // subarray of length k tec += mov; b[i + ( int )k] = mov; } } // Number of moves // should not exceed m return ans <= m; } // Function to find the maximum // value of the smallest array // element that can be obtained static long FindLargest( long [] a) { l = 1 ; r = ( long )Math.pow( 10 , 10 ); // Perform Binary search while (r - l > 0 ) { long tm = (l + r + 1 ) / 2 ; if (check(tm, a)) l = tm; else r = tm - 1 ; } return l; } // Driver Code public static void main(String[] args) { // Given Input long [] a = { 2 , 2 , 2 , 2 , 1 , 1 }; m = 2 ; k = 3 ; n = a.length; // Function Call System.out.println(FindLargest(a)); } } // This code is contributed by hritikrommie. |
Python3
# Python 3 program for above approach n = 0 m = 0 k = 0 l = 0 r = 0 i = 0 from math import pow # Function to check if the smallest # value of v is achievable or not def check(v, a): tec = 0 ans = 0 # Create array to # store previous moves b = [ 0 for i in range (n + k + 1 )] for i in range (n): # Remove previous moves tec - = b[i] if (a[i] + tec < v): # Add balance to ans mov = v - a[i] - tec ans = ans + mov # Update contiguous # subarray of length k tec + = mov b[i + k] = mov # Number of moves # should not exceed m return (ans < = m) # Function to find the maximum # value of the smallest array # element that can be obtained def FindLargest(a): l = 1 r = pow ( 10 , 10 ) # Perform Binary search while (r - l > 0 ): tm = (l + r + 1 ) / / 2 if (check(tm, a)): l = tm else : r = tm - 1 return l # Driver Code if __name__ = = '__main__' : # Given Input a = [ 2 , 2 , 2 , 2 , 1 , 1 ] m = 2 k = 3 n = len (a) # Function Call print ( int (FindLargest(a))) # This code is contributed by ipg2016107. |
C#
// C# program for above approach using System; public class GFG { static long n, m, k, l, r, i; // Function to check if the smallest // value of v is achievable or not static bool check( long v, long [] a) { long tec = 0, ans = 0; // Create array to // store previous moves long [] b = new long [( int )(n + k + 1)]; for ( int i = 0; i < n; i++) { // Remove previous moves tec -= b[i]; if (a[i] + tec < v) { // Add balance to ans long mov = v - a[i] - tec; ans = ans + mov; // Update contiguous // subarray of length k tec += mov; b[i + ( int )k] = mov; } } // Number of moves // should not exceed m return ans <= m; } // Function to find the maximum // value of the smallest array // element that can be obtained static long FindLargest( long [] a) { l = 1; r = ( long )Math.Pow(10, 10); // Perform Binary search while (r - l > 0) { long tm = (l + r + 1) / 2; if (check(tm, a)) l = tm; else r = tm - 1; } return l; } // Driver Code public static void Main(String[] args) { // Given Input long [] a = { 2, 2, 2, 2, 1, 1 }; m = 2; k = 3; n = a.Length; // Function Call Console.WriteLine(FindLargest(a)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program for above approach let n = 0, m = 0, k = 0, l = 0, r = 0, i = 0; // Function to check if the smallest // value of v is achievable or not function check(v, a) { let tec = 0, ans = 0; // Create array to // store previous moves let b = new Array(n + k + 1).fill(0); for (i = 0; i < n; i++) { // Remove previous moves tec -= b[i]; if (a[i] + tec < v) { // Add balance to ans let mov = v - a[i] - tec; ans = ans + mov; // Update contiguous // subarray of length k tec += mov; b[i + k] = mov; } } // Number of moves // should not exceed m return ans <= m; } // Function to find the maximum // value of the smallest array // element that can be obtained function FindLargest(a) { l = 1; r = Math.pow(10, 10); // Perform Binary search while (r - l > 0) { let tm = Math.floor((l + r + 1) / 2); if (check(tm, a)) l = tm; else r = tm - 1; } return l; } // Driver Code // Given Input let a = [ 2, 2, 2, 2, 1, 1 ]; m = 2; k = 3; n = a.length; // Function Call document.write(FindLargest(a)); // This code is contributed by _saurabh_jaiswal </script> |
2
Time Complexity: O(NlogN)
Auxiliary Space: O(N + K)
Contact Us