Minimize the maximum value in array by incrementing and decrementing.
Given array arr[] of size N, the task is to minimize the maximum value in given array by increasing arr[i] by 1 and decreasing arr[i + 1] by 1 any number of times.
Examples:
Input: arr[] = {3, 7, 1, 6}
Output: 5
Explanation: Initially we have arr[] = {3, 7, 1, 6}
- Choose i = 1 (considering 1 index), arr[] becomes {4, 6, 1, 6}
- Choose i = 1, arr[] becomes {5, 5, 1, 6}
- Choose i = 3, arr[] becomes {5, 5, 2, 5}
5 is the minimum number we can get by performing above operations any number of timesInput: arr[] = {10, 1}
Output: 10
Explanation: 10 is the minimum number we can get by performing above operations any number of times.
Approach: Implement the idea below to solve the problem
Binary Search can be used to solve this problem. Idea is for every number we can check whether it is possible to make it as maximum element of array or not by performing given operations. We will binary search on this monotonic function it will be of type FFFFFTTTTT initially function will be false for smaller values and as the values increase it will keep returning true. We have to find first time when function becomes true.
Step-by-step approach:
- Declare function test() to check if it is possible to make maximum value of array at most mid
- Declare variable prev which is initially set to zero (which is extra number that we need to carry backwards so to make i’th element at most mid)
- Iterate i from N – 1 to 1 and follow given steps for each i:
- if sum of A[i] and prev is greater than mid update prev as A[i] + prev – mid
- else make prev as 0
- finally return whether sum of first element and prev is less than equal to mid or not
- Declare low = 0 and high as sum of array A[]
- Run while loop till high and low are not adjacent
- Declare variable mid set as (low + high) / 2
- if test function is true for mid update high as mid otherwise low as mid + 1
- if test() function is true for low return low otherwise return high
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // mod number const int mod = 1e9 + 7; // to avoid interger overflow #define int long long // Function to Minimize the maximum value by performing // given operations on adjacent elements int minimizeMaximumVal( int A[], int N) { // function to check if it is possible to make maximum // element of array at most mid auto test = [&]( int mid) -> bool { // keeps track of previous extra (greater than mid) int prev = 0; // iterate from N - 1 to 1 for ( int i = N - 1; i >= 1; i--) { // check if i'th element and previous extra is // greater than mid or not if (A[i] + prev > mid) { prev = A[i] + prev - mid; } else prev = 0; } return A[0] + prev <= mid; }; // range of binary search int low = 0, high = accumulate(A, A + N, 0LL); // keep running while loop till high and low are not // adjacent while (high - low > 1) { // Declare variable to find mid of low and high int mid = (low + high) / 2; // if it is possible to make maximum element of // array A[] at most mid if (test(mid)) { high = mid; } else { low = mid + 1; } } // if it is possible to make maximum element of // array A[] as low if (test(low)) return low; // otherwise high else return high; } // Driver Code int32_t main() { // Input int N = 4; int A[] = { 3, 7, 1, 6 }; // Function Call cout << minimizeMaximumVal(A, N) << endl; return 0; } |
Java
class Main { // Function to check if it is possible to make the // maximum element of the array at most mid static boolean test( int mid, int [] A, int N) { // Keeps track of previous extra (greater than mid) int prev = 0 ; // Iterate from N - 1 to 1 for ( int i = N - 1 ; i > 0 ; i--) { // Check if i'th element and previous extra is // greater than mid or not if (A[i] + prev > mid) { prev = A[i] + prev - mid; } else { prev = 0 ; } } return A[ 0 ] + prev <= mid; } // Function to minimize the maximum value by performing // given operations on adjacent elements static int minimizeMaximumValue( int [] A, int N) { // Range of binary search int low = 0 , high = 0 ; for ( int value : A) { high += value; } // Keep running the while loop until high and low // are not adjacent while (high - low > 1 ) { // Declare variable to find mid of low and high int mid = (low + high) / 2 ; // If it is possible to make the maximum element // of array A[] at most mid if (test(mid, A, N)) { high = mid; } else { low = mid + 1 ; } } // If it is possible to make the maximum element of // array A[] as low if (test(low, A, N)) { return low; } else { // Otherwise high return high; } } // Driver Code public static void main(String[] args) { // Input int N = 4 ; int [] A = { 3 , 7 , 1 , 6 }; // Function Call System.out.println(minimizeMaximumValue(A, N)); } } |
C#
using System; class Program { // mod number const int Mod = 1000000007; // Function to minimize the maximum value by performing // given operations on adjacent elements static bool Test( long mid, long [] A, int N) { // Keeps track of previous extra (greater than mid) long prev = 0; // Iterate from N - 1 to 1 for ( int i = N - 1; i >= 1; i--) { // Check if i'th element and previous extra is // greater than mid or not if (A[i] + prev > mid) { prev = A[i] + prev - mid; } else { prev = 0; } } return A[0] + prev <= mid; } // Function to minimize the maximum value by performing // given operations on adjacent elements using binary search static long MinimizeMaximumVal( long [] A, int N) { // Range of binary search long low = 0, high = 0; // Calculate the sum of all array elements for ( int i = 0; i < N; i++) { high += A[i]; } // Keep running while loop until high and low are not adjacent while (high - low > 1) { // Declare variable to find mid of low and high long mid = (low + high) / 2; // If it is possible to make the maximum element of // array A[] at most mid if (Test(mid, A, N)) { high = mid; } else { low = mid + 1; } } // If it is possible to make the maximum element of // array A[] as low if (Test(low, A, N)) return low; // Otherwise high else return high; } // Driver Code static void Main() { // Example input values int N = 4; long [] A = { 3, 7, 1, 6 }; // Print the result of the MinimizeMaximumVal function Console.WriteLine(MinimizeMaximumVal(A, N)); } } // This code is contributed by shivamgupta310570 |
Javascript
// JavaScript Implementation // Function to minimize the maximum value by performing // given operations on adjacent elements function minimize_maximum_val(A, N) { // Function to check if it is possible to make maximum // element of array at most mid function test(mid) { // Keeps track of previous extra (greater than mid) let prev = 0; // Iterate from N - 1 to 1 for (let i = N - 1; i > 0; i--) { // Check if i'th element and previous extra is // greater than mid or not if (A[i] + prev > mid) { prev = A[i] + prev - mid; } else { prev = 0; } } return A[0] + prev <= mid; } // Range of binary search let low = 0; let high = A.reduce((a, b) => a + b, 0); // Keep running while loop till high and low are not // adjacent while (high - low > 1) { // Declare variable to find mid of low and high let mid = Math.floor((low + high) / 2); // If it is possible to make the maximum element of // array A[] at most mid if (test(mid)) { high = mid; } else { low = mid + 1; } } // If it is possible to make the maximum element of // array A[] as low if (test(low)) { return low; } else { return high; } } // Driver Code const N = 4; const A = [3, 7, 1, 6]; // Function Call console.log(minimize_maximum_val(A, N)); // This code is contributed by Sakshi |
Python3
# Python code to implement the approach # Function to minimize the maximum value by performing # given operations on adjacent elements def minimize_maximum_val(A, N): # function to check if it is possible to make maximum # element of array at most mid def test(mid): # keeps track of previous extra (greater than mid) prev = 0 # iterate from N - 1 to 1 for i in range (N - 1 , 0 , - 1 ): # check if i'th element and previous extra is # greater than mid or not if A[i] + prev > mid: prev = A[i] + prev - mid else : prev = 0 return A[ 0 ] + prev < = mid # range of binary search low, high = 0 , sum (A) # keep running while loop till high and low are not # adjacent while high - low > 1 : # Declare variable to find mid of low and high mid = (low + high) / / 2 # if it is possible to make the maximum element of # array A[] at most mid if test(mid): high = mid else : low = mid + 1 # if it is possible to make the maximum element of # array A[] as low if test(low): return low # otherwise high else : return high # Driver Code if __name__ = = "__main__" : # Input N = 4 A = [ 3 , 7 , 1 , 6 ] # Function Call print (minimize_maximum_val(A, N)) |
5
Time Complexity: O(N log (N))
Auxiliary Space: O(N)