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 = 14At 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++
// C++ Code for the Approach#include <bits/stdc++.h>using namespace std;// User function Templateint getMinDiff(int arr[], int n, int k){ sort(arr, arr + n); // Maximum possible height difference 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 on subtracting k we got // negative then continue if (arr[i] - k < 0) continue; // Minimum element when we // add k to whole array tempmin = min(arr[0] + k, arr[i] - k); // Maximum element when we // subtract k from whole array tempmax = max(arr[i - 1] + k, arr[n - 1] - k); ans = min(ans, tempmax - tempmin); } return ans;}// Driver Code Startsint main(){ int k = 6, n = 6; int arr[n] = { 7, 4, 8, 8, 8, 9 }; // Function Call int ans = getMinDiff(arr, n, k); cout << ans;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;// Driver codepublic 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); } // User function Template for Java public static int getMinDiff(int[] arr, int n, int k) { Arrays.sort(arr); // Maximum possible height difference 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 on subtracting k we got negative then // continue if (arr[i] - k < 0) continue; // Minimum element when we add k to whole array tempmin = Math.min(arr[0] + k, arr[i] - k); // Maximum element when we subtract k from whole // array tempmax = Math.max(arr[i - 1] + k, arr[n - 1] - k); ans = Math.min(ans, tempmax - tempmin); } return ans; }} |
Python3
# User function Templatedef getMinDiff(arr, n, k): arr.sort() ans = arr[n - 1] - arr[0] # Maximum possible height difference 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) # Minimum element when we # add k to whole array # Maximum element when we tempmax = max(arr[i - 1] + k, arr[n - 1] - k) # subtract k from whole array ans = min(ans, tempmax - tempmin) return ans# Driver Code Startsk = 6n = 6arr = [7, 4, 8, 8, 8, 9]ans = getMinDiff(arr, n, k)print(ans)# This code is contributed by ninja_hattori. |
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); // Maximum possible height difference int tempmax = arr[n - 1] - k; // Maximum element when we // subtract k from whole array int tempmin = arr[0] + k; // Minimum element when we // add k to whole array 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); }}// This code is contributed by ninja_hattori. |
Javascript
<script>// User function Templatefunction getMinDiff(arr,n,k){ arr.sort((a,b) => (a-b)) let ans = arr[n - 1] - arr[0]; // Maximum possible height difference 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); // Minimum element when we // add k to whole array tempmax = Math.max(arr[i - 1] + k, arr[n - 1] - k); // Maximum element when we // subtract k from whole array ans = Math.min(ans, tempmax - tempmin); } return ans;}// Driver Code Startslet k = 6, n = 6;let arr = [ 7, 4, 8, 8, 8, 9 ];let ans = getMinDiff(arr, n, k);document.write(ans,"</br>");//This code is contributed by shinjanpatra.</script> |
5
Time Complexity: O(N * log(N)), Time is taken for sorting
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
[…] View […]