Last Updated: 3 Sep, 2020
Minimize The Maximum
Easy
Asked in companies
You are given an array of N integers and an integer K. For each array element, you are allowed to increase or decrease it by a value k. The task is to minimize the difference between the maximum element and the minimum element after modifications.
Input Format :
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the test cases follow.
The first line of each test case contains a positive integer N which represents the number of elements of an array.
The Second line of each test case contains N integers denoting the elements of the array.
The third line of each test case contains a positive integer K.
Output Format :
For each test case, return the minimum difference between the maximum element and minimum element of the array by either increasing or decreasing elements of the array by K.
Note:
You do not need to print anything. It has already been taken care of.
Constraints :
1 <= T <= 5
1 <= N <= 10^5
0 <= arr[i] <= 10^5
0 <= K <= 10^5
Time limit = 1 sec
Approaches
For every element, we have two choices either increase it by k or decrease it by k.
- Initialize a global variable ans to the maximum value.
- Call a helper function that takes an array, k, index, and min and max as arguments, where min will be initialized to maximum value and minimum will be initialized to the minimum value.
- Check for the base condition if the whole array is processed then update the ans with the minimum of ans and difference between max and min.
- Now for every element, call the helper function two times,
- Update the max and min by increasing the element at index by k.
- Update the max and min by decreasing the element at index by k.
- Finally, return ans.
The big thing to observe is that for any given element, if you choose to increase its height from hi to hi + k, then you might as well increase all shorter elements: that won't affect the maximum (because if hj < hi, then hj + k < hi + k), and may help by increasing the minimum. Conversely, if you choose to decrease the height of a tower from hi to hi − k, then you might as well decrease the heights of all taller towers.
So, for every element at index i, we will increment all the elements which are smaller than that element by k and decrement all elements which are larger or equal to that element by k. Thus the minimum of the array would be either arr[0]+k or arr[i]-k. And the maximum of the array would be either arr[n-1]-k or arr[i-1]+k.
Approach:
- Sort the array in ascending order.
- Initialize the variable result with the difference between the first and the last element of the array.
- Run a loop for one to the length of the array.
- initialize the variable min to the minimum of (arr[0] +k, arr[i]-k).
- initialize the variable max to the maximum of (arr[n-1] -k, arr[i-1]+k).
- Update the result with the minimum of the result and the difference between max and min.
- Return the result.
Similar problems