Given an array arr[] 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.
Input: k = 3, n = 5, arr[] = {3, 9, 12, 16, 20}
Output: 11
Input: k = 2, n = 4, arr[] = {1, 5, 8, 10}
Output: 5
Solutions
Method 1: Using Sorting
Follow the steps below to solve the given problem:
Sort the array.
Now current "minHeight" would be the element at the "0th" index (arr[0]), current "maxHeight" would be the element at the "n-1th" index (arr[n-1]) and current "minDiff" would be "arr[n-1]-arr[0]".
But, this is not necessarily the minimum difference possible between two towers, so we loop through the array to find the minimum difference if any.
In each iteration:
1) We will consider two adjacent elements, "i" and "i-1" so the loop will run from "1" to "n".
2) If the current element "arr[i]" is less than "k", continue, because this will turn a tower height (arr[i]-k) negative.
3) Find "minHeight" as "min(arr [0] + k, arr [i] - k)" and "maxHeight" as "max(arr [i - 1] + k, arr [n - 1] - k)".
4) Return, min (maxHeight-minHeight, minDiff).
Complexity
The time complexity of this solution is O(n log n) and space complexity is O(1).