# Minimize the maximum difference between the heights

Hello Everyone,

Given heights of n towers and a value k. We need to either increase or decrease the height of every tower by k (only once) where k > 0. The task is to minimize the difference between the heights of the longest and the shortest tower after modifications and output this difference.
Examples:

Input : arr[] = {1, 15, 10}, k = 6
Output : Maximum difference is 5.
Explanation : We change 1 to 7, 15 to
9 and 10 to 4. Maximum difference is 5
(between 4 and 9). We can’t get a lower
difference.

Input : arr[] = {1, 5, 15, 10}
k = 3
Output : Maximum difference is 8
arr[] = {4, 8, 12, 7}

Input : arr[] = {4, 6}
k = 10
Output : Maximum difference is 2
arr[] = {14, 16} OR {-6, -4}

Input : arr[] = {6, 10}
k = 3
Output : Maximum difference is 2
arr[] = {9, 7}

Input : arr[] = {1, 10, 14, 14, 14, 15}
k = 6
Output: Maximum difference is 5
arr[] = {7, 4, 8, 8, 8, 9}

Input : arr[] = {1, 2, 3}
k = 2
Output: Maximum difference is 2
arr[] = {3, 4, 5}

First we try to sort the array and make each height of the tower maximum . We do this by decreasing the height of all the towers towards right by k and increasing all the height of the towers towards left (by k). It is also possible that the tower you are trying to increase the height doesn’t have the maximum height . Therefore we only need to check whether it has the maximum height or not by comparing it with the last element towards the right side which is an-k. Since the array is sorted if the tower’s height is greater than the an-k then it’s the tallest tower available. Similar reasoning can also be applied for finding the shortest tower .

Note:- We need not consider where a[i]<k because the height of the tower can’t be negative

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`// User function template for C++`

`class` `Solution {`

`public` `:`

` ` `//function to find the minimum possible difference between maximum and minimum elements when we have to add/subtract every number by k`

` ` `int` `getMinDiff(` `int` `arr[], ` `int` `n, ` `int` `k)`

` ` `{`

` ` `sort(arr, arr + n);` `//sort the array to get the corner cases ans.`

` ` `int` `minEle, maxEle;` `//these 2 variables will hold the between elements max and min value`

` ` `int` `result = arr[n - 1] - arr;` `//current result when arr iss min and arr[n-1] is max`

` ` `for` `(` `int` `i = 1; i <= n - 1; i++) {`

` ` `maxEle = max(arr[i - 1] + k, arr[n - 1] - k);` `//`

` ` `minEle = min(arr + k, arr[i] - k);`

` ` `result = min(result, maxEle - minEle);` `//if the middle elements max and min diffrence if less than result then update result.`

` ` `}`

` ` `return` `result;` `//return result.`

` ` `}`

`};`

`// Driver Code`

`int` `main()`

`{`

` ` `int` `t=1;`

` `

` ` `while` `(t--) {`

` ` `int` `k = 6;`

` ` `int` `n=3;`

` ` `int` `arr[n]={1, 15, 10};`

` `

` `

` ` `Solution ob;`

` ` `auto` `ans = ob.getMinDiff(arr, n, k);`

` ` `cout << ans << ` `"\n"` `;`

` ` `}`

` ` `return` `0;`

`}`

Output:-

5

Time Complexity: O(nlogn)