Minimize The Difference

Easy
0/40
Average time to solve is 20m
profile
Contributed by
177 upvotes
Asked in companies
FlipkartIntuitNagarro Software

Problem statement

You are given an array ‘A’ of length ‘N’ consisting only of positive integers and an integer ‘K’. You have to update every element of the array by increasing or decreasing its value by ‘K’ only once. Your task is to minimize the difference between maximum and minimum elements of the array after performing the increment or decrement on every element of the array.

Note: After the operation, every value of the array should remain non-negative.

For example:

Let’s say the array ‘A’ = [1, 2, 3, 4, 5] and ‘K’ = 2, then after increasing each element by ‘K’. The array ‘A’ will become [3, 4, 5, 6, 7]. So the maximum - minimum will be 7 - 3 = 4. 
Detailed explanation ( Input/output format, Notes, Images )
Input Format-
First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains two space-separated integers, ‘N’ and ‘K’, denoting the length of the array ‘A’ and the amount you must increase or decrease, respectively.
The following line contains ‘N’ space-separated positive integers, representing the array’s values. 
Output Format-
For each test case, you have to print an integer denoting the minimum difference between maximum and minimum elements of the array after performing the increment or decrement on every element of the array.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints -
1 <= ‘T’ <= 5
1 <= ‘N’ <= 10^5
1 <= ‘K’ <= 10^9
1 <= A[i] <= 10^9, for 1 <= i <= ‘N’
Note- Sum of ‘N’ over all test cases does not exceed 10^5.

Time Limit: 1 sec
Sample Input-1
2
4 2
1 5 8 10
5 2
1 2 3 4 5
Sample Output-1
5
3
Explanation for Sample Input 1:
For test case 1:
    The final array will look like [3, 3, 6, 8]. So the difference between maximum and minimum is 8 - 3 = 5.
For test case 2:
    The final array will look like [3, 4, 1, 2, 3]. So the difference between maximum and minimum is 4 - 1 = 3.
Sample Input -2
2
1 2
8
3 2
1 3 3
Sample Output -2
0
2
Hint

How does the maximum and minimum element change when applying the operation?

Approaches (1)
Greedy

Approach: we sort the given array, and then for each index, we perform the decrement operation on all the indexes greater than index ‘i’ and increment operation until the index ‘i’. Find the difference between maximum and minimum and update the answer. This works because we decrease all the greater values and increase the smaller ones, ultimately leading to a smaller difference.

 

Algorithm:

  • Sort ‘A’.
  • Create a variable, ‘ans’, and initialize it to the difference between the last and first terms of ‘A’.
  • Create two variables, ‘minimum’ and ‘maximum’ and initialize them to ‘A[0] + K’ and ‘A[N - 1] - K’, respectively.
  • Create two variables, ‘current_minimum’ and ‘current_maximum’.
  • Iterate using a for loop from i = ‘0’ to ‘N - 1’.
    • Update ‘current_minimum’ to min(minimum, A[i + 1] - K).
    • Update ‘current_maximum’ to max(maximum, A[i] + K).
    • If ‘current_minimum’ is non-negative.
      • Update ‘ans’ to min(ans, current_maximum - current_minimum).
  • Print ‘ans’.
Time Complexity

O(N * log(N)). Where ‘N’ is the length of the array.

We are sorting the array. Hence the overall complexity is O(N * log(N).

Space Complexity

O(1).

We are creating five variables. Hence the overall complexity is O(1).

Code Solution
(100% EXP penalty)
Minimize The Difference
Full screen
Console