# Minimum difference between heights of Towers

Given an array a[] denoting heights of **n **towers and a positive integer **k**, you have to modify the height of each tower either by increasing or decreasing them by K only once. After modifying, height should be a non-negative integer.

Find out what could be the possible minimum difference of the height of shortest and longest towers after you have modified each tower.

Example 1:

```
Input:
k = 2, n = 4
Arr[] = {1, 5, 8, 10}
Output:
5
Explanation:
The array can be modified as
{3, 3, 6, 8}. The difference between
the largest and the smallest is 8-3 = 5.
```

Example 2:

```
Input:
k = 3, n = 5
Arr[] = {3, 9, 12, 16, 20}
Output:
11
Explanation:
The array can be modified as
{6, 12, 9, 13, 17}. The difference between
the largest and the smallest is 17-6 = 11.
```

first sort the original heights and numbering them in increasing order, so that *h*_{1} is the original height of the originally-shortest tower and *h*_{n} is the original height of the originally-tallest tower.

For each *i*, try the possibility that the *i*th-shortest tower is the tallest tower that we increase the height of; that is, try the possibility that we increase *h*_{1} through *h*_{i} and decrease *h*_{i+1} through *h*_{n}. There are two groups of cases:

- If
*i*<*n*, then the final height of the finally-shortest tower is min(*h*_{1}+*k*,*h*_{i+1}−*k*), and the final height of the finally-tallest tower is max(*h*_{i}+*k*,*h*_{n}−*k*). The final difference in this case is the latter minus the former. - If
*i*=*n*, then we've increased the heights of all towers equally, so the final difference is just*h*_{n}−*h*_{1}.

We then take the least difference from all *n* of these possibilities.

**c++ implementation:**

int getMinDiff(int a[], int n, int k) { sort(a, a+n); int mi, ma; int ans = a[n-1] - a[0]; for(int i =1; i<=n-1; i++) { if(a[i]>=k) { ma = max(a[i-1] + k, a[n-1]-k); mi = min(a[0]+k, a[i]-k); ans = min(ans, ma-mi); } } return ans; }

**Time Complexity:**O(nlogn)

**space Complexity:**O(1)