Minimize The Maximum

Easy

0/40

Average time to solve is 15m

Contributed by

18 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

Sample Output 1:

Explanation For Sample Input 1 :

Arrays that can be obtained by either increasing or decreasing each element by k are

[-5 9 4]   difference between maximum and minimum is 16

[-5 9 16] difference between maximum and minimum is 21

[-5 21 16] difference between maximum and minimum is 26

[-5 21 4] difference between maximum and minimum is 26

[7 9 4]   difference between maximum and minimum is 5

[7 9 16] difference between maximum and minimum is 9

[7 21 16] difference between maximum and minimum is 14

[7 21 4] difference between maximum and minimum is 17

So the minimum of all differences between maximum and minimum elements is 5. So, we need to return 5.

Sample Input 2 :

Sample Output 2:

Hint 1

Hint 2

Think of brute force.

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

O(2^N), where N is the length of the array.

Since for every element, we are either increasing it or decreasing it by k.

Space Complexity

O(N), where N is the length of the array.

As in recursion, we are using stack space.

(100% EXP penalty)

Minimize The Maximum

Console