PROBLEM DESCRIPTION
Given an array arr[] denoting heights of N towers and a positive integer K.
For each tower, you must perform exactly one of the following operations exactly once.
- Increase the height of the tower by
K - Decrease the height of the tower by
K
Find out the minimum possible difference between the height of the shortest and tallest towers after you have modified each tower.
Note: It is compulsory to increase or decrease the height by K for each tower. After the operation, the resultant array should not contain any negative integers.
SOLUTION
Good Explanation - GeeksForGeeks
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
int getMinDiff(int[] arr, int n, int k) {
Arrays.sort(arr);
int res = arr[n-1] - arr[0];
int smallest = arr[0] + k;
int largest = arr[n-1] - k;
int mi = 0;
int ma = 0;
for(int i=0; i<n-1; i++){
mi = Math.min(smallest, arr[i+1] - k);
ma = Math.max(largest, arr[i] + k);
if(mi < 0) continue;
res = Math.min(res, ma - mi);
}
return res;
}
}