Given the heights of N towers and a value of K, Either increase or decrease the height of every tower by K (only once) where K > 0. After modifications, the task is to minimize the difference between the heights of the longest and the shortest tower and output its difference.
Examples:
Input: arr[] = {1, 15, 10}, k = 6
Output: Maximum difference is 5.
Explanation: 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}
The idea for this is given below:
- The idea is to increase the first i towers by k and decrease the rest tower by k after sorting the heights, then calculate the maximum height difference.
- This can be achieved using sorting.
Illustration:
Given arr[] = {1, 15, 10}, n = 3, k = 6
Array after sorting => arr[] = {1, 10, 15}
Initially maxHeight = arr[n – 1] = 15
minHeight = arr[0] = 1
ans = maxHeight – minHeight = 15 – 1 = 14
At i = 1
- minHeight = min(arr[0] + k, arr[i] – k) = min(1 + 6, 10 – 6) = 4
- maxHeight = max(arr[i – 1] + k, arr[n – 1] – k) = max(1 + 6, 15 – 6) = 9
- ans = min(ans, maxHeight – minHeight) = min(14, 9 – 4) = 5 => ans = 5
At i = 2
- minHeight = min(arr[0] + k, arr[i] – k) = min(1 + 6, 15 – 6) = 7
- maxHeight = max(arr[i – 1] + k, arr[n – 1] – k) = max(10 + 6, 15 – 6) = 16
- ans = min(ans, maxHeight – minHeight) = min(5, 16 – 7) = 5 => ans = 5
Hence minimum difference is 5
Note:- Consider where a[i] < K because the height of the tower can’t be negative so neglect that case. You may wonder that if we neglect this case, then we would also be neglecting a[i-1] + k; what if it is greater than a[n-1]-k? The answer for that is because a[i] < K, we don’t have any other option than to increase its height by K. And because a[i] > a[i-1], hence a[i] + k would also be greater than a[i-1]+k. Therefore, a[i-1] + k would never be the maximum height of the array and hence can be neglected.
Furthermore, the reason we don’t take a[i] for both minHeight and maxHeight is because it is possible that a[i] – k < arr[0] +k and at the same time a[i] +k > a[n-1] – k. In this scenario, we would be both increasing and decreasing the height of the tower which is not possible.
Follow the steps below to solve the given problem:
- Sort the array
- Try to make each height of the tower maximum by decreasing the height of all the towers to the right by k and increasing all the height of the towers to the left by k. Check whether the current index tower has the maximum height or not by comparing it with a[n]-k. If the tower’s height is greater than the a[n]-k then it’s the tallest tower available.
- Similarly, find the shortest tower and minimize the difference between these two towers.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int getMinDiff(int arr[], int n, int k)
{
sort(arr, arr + n);
int ans = arr[n - 1] - arr[0];
int tempmin, tempmax;
tempmin = arr[0];
tempmax = arr[n - 1];
for (int i = 1; i < n; i++) {
if (arr[i] - k < 0)
continue;
tempmin = min(arr[0] + k, arr[i] - k);
tempmax = max(arr[i - 1] + k, arr[n - 1] - k);
ans = min(ans, tempmax - tempmin);
}
return ans;
}
int main()
{
int k = 6, n = 6;
int arr[n] = { 7, 4, 8, 8, 8, 9 };
int ans = getMinDiff(arr, n, k);
cout << ans;
}
|
Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args)
{
int[] arr = { 7, 4, 8, 8, 8, 9 };
int k = 6;
int ans = getMinDiff(arr, arr.length, k);
System.out.println(ans);
}
public static int getMinDiff(int[] arr, int n, int k)
{
Arrays.sort(arr);
int ans = arr[n - 1] - arr[0];
int tempmin, tempmax;
tempmin = arr[0];
tempmax = arr[n - 1];
for (int i = 1; i < n; i++) {
if (arr[i] - k < 0)
continue;
tempmin = Math.min(arr[0] + k, arr[i] - k);
tempmax
= Math.max(arr[i - 1] + k, arr[n - 1] - k);
ans = Math.min(ans, tempmax - tempmin);
}
return ans;
}
}
|
Python3
def getMinDiff(arr, n, k):
arr.sort()
ans = arr[n - 1] - arr[0]
tempmin = arr[0]
tempmax = arr[n - 1]
for i in range(1, n):
if arr[i] < k:
continue
tempmin = min(arr[0] + k, arr[i] - k)
tempmax = max(arr[i - 1] + k, arr[n - 1] - k)
ans = min(ans, tempmax - tempmin)
return ans
k = 6
n = 6
arr = [7, 4, 8, 8, 8, 9]
ans = getMinDiff(arr, n, k)
print(ans)
|
C#
using System;
public class GFG {
static public int getMinDiff(int[] arr, int n, int k)
{
Array.Sort(arr);
int ans
= (arr[n - 1] + k)
- (arr[0]
+ k);
int tempmax
= arr[n - 1] - k;
int tempmin = arr[0] + k;
int max, min;
for (int i = 0; i < n - 1; i++) {
if (tempmax > (arr[i] + k)) {
max = tempmax;
}
else {
max = arr[i] + k;
}
if (tempmin < (arr[i + 1] - k)) {
min = tempmin;
}
else {
min = arr[i + 1] - k;
}
if (ans > (max - min)) {
ans = max - min;
}
}
return ans;
}
static public void Main()
{
int[] arr = { 7, 4, 8, 8, 8, 9 };
int k = 6;
int ans = getMinDiff(arr, arr.Length, k);
Console.Write(ans);
}
}
|
Javascript
<script>
function getMinDiff(arr,n,k)
{
arr.sort((a,b) => (a-b))
let ans = arr[n - 1] - arr[0];
let tempmin, tempmax;
tempmin = arr[0];
tempmax = arr[n - 1];
for (let i = 1; i < n; i++) {
tempmin= Math.min(arr[0] + k,arr[i] - k);
tempmax = Math.max(arr[i - 1] + k, arr[n - 1] - k);
ans = Math.min(ans, tempmax - tempmin);
}
return ans;
}
let k = 6, n = 6;
let arr = [ 7, 4, 8, 8, 8, 9 ];
let ans = getMinDiff(arr, n, k);
document.write(ans,"</br>");
</script>
|
Time Complexity: O(N * log(N)), Time is taken for sorting
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!