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₁ 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 ith-shortest tower is the tallest tower that we increase the height of; that is, try the possibility that we increase h₁ 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₁ + 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₁.

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)