Maximize the smallest array element by incrementing all elements in a K-length s...
source link: https://www.geeksforgeeks.org/maximize-the-smallest-array-element-by-incrementing-all-elements-in-a-k-length-subarray-by-1-exactly-m-times/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Maximize the smallest array element by incrementing all elements in a K-length subarray by 1 exactly M times
- Difficulty Level : Medium
- Last Updated : 13 Aug, 2021
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:
- Python3
- Javascript
// C++ program for above approach#include <bits/stdc++.h>using namespace std;#define ll long longll n, m, k, l, r, i;// Function to check if the smallest// value of v is achievable or notll check(ll v, vector<ll>& a){ll tec = 0, ans = 0;// Create array to// store previous movesvector<ll> b(n + k + 1);for (i = 0; i < n; i++) {// Remove previous movestec -= b[i];if (a[i] + tec < v) {// Add balance to ansll mov = v - a[i] - tec;ans = ans + mov;// Update contiguous// subarray of length ktec += mov;b[i + k] = mov;}}// Number of moves// should not exceed mreturn (ans <= m);}// Function to find the maximum// value of the smallest array// element that can be obtainedll FindLargest(vector<ll> a){l = 1;r = pow(10, 10);// Perform Binary searchwhile (r - l > 0) {ll tm = (l + r + 1) / 2;if (check(tm, a))l = tm;elser = tm - 1;}return l;}// Driver Codeint main(){// Given Inputvector<ll> a{ 2, 2, 2, 2, 1, 1 };m = 2;k = 3;n = a.size();// Function Callcout << FindLargest(a);return 0;} |
2
Time Complexity: O(NlogN)
Auxiliary Space: O(N + K)
.png)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK