Tutorialspoint.dev

Minimize the maximum difference between the heights

Given heights of n towers and a value k. We need to either increase or decrease 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 6, 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} 

Source : Adobe Interview Experience | Set 24 (On-Campus for MTS)



The idea is to sort all elements increasing order.

Below is implementation of above idea.

C++

// C++ program to find the minimum possible
// difference between maximum and minimum
// elements when we have to add/subtract
// every number by k
#include <bits/stdc++.h>
using namespace std;
  
// Modifies the array by subtracting/adding
// k to every element such that the difference
// between maximum and minimum is minimized
int getMinDiff(int arr[], int n, int k)
{
    if (n == 1)
       return 0;
  
    // Sort all elements
    sort(arr, arr+n);
  
    // Initialize result
    int ans = arr[n-1] - arr[0];
  
    // Handle corner elements
    int small = arr[0] + k;
    int big = arr[n-1] - k;
    if (small > big)
       swap(small, big);
  
    // Traverse middle elements
    for (int i = 1; i < n-1; i ++)
    {
        int subtract = arr[i] - k;
        int add = arr[i] + k;
  
        // If both subtraction and addition
        // do not change diff
        if (subtract >= small || add <= big)
            continue;
  
        // Either subtraction causes a smaller
        // number or addition causes a greater
        // number. Update small or big using
        // greedy approach (If big - subtract
        // causes smaller diff, update small
        // Else update big)
        if (big - subtract <= add - small)
            small = subtract;
        else
            big = add;
    }
  
    return  min(ans, big - small);
}
  
// Driver function to test the above function
int main()
{
    int arr[] = {4, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 10;
    cout << " Maximum difference is "
        << getMinDiff(arr, n, k);
    return 0;
}

Java

// Java program to find the minimum possible
// difference between maximum and minimum
// elements when we have to add/subtract
// every number by k
import java.util.*;
  
class GFG {
  
    // Modifies the array by subtracting/adding
    // k to every element such that the difference
    // between maximum and minimum is minimized
    static int getMinDiff(int arr[], int n, int k)
    {
        if (n == 1)
        return 0;
  
        // Sort all elements
        Arrays.sort(arr);
  
        // Initialize result
        int ans = arr[n-1] - arr[0];
  
        // Handle corner elements
        int small = arr[0] + k;
        int big = arr[n-1] - k;
        int temp = 0;
          
        if (small > big)
        {
            temp = small;
            small = big;
            big = temp;
        }
  
        // Traverse middle elements
        for (int i = 1; i < n-1; i ++)
        {
            int subtract = arr[i] - k;
            int add = arr[i] + k;
  
            // If both subtraction and addition
            // do not change diff
            if (subtract >= small || add <= big)
                continue;
  
            // Either subtraction causes a smaller
            // number or addition causes a greater
            // number. Update small or big using
            // greedy approach (If big - subtract
            // causes smaller diff, update small
            // Else update big)
            if (big - subtract <= add - small)
                small = subtract;
            else
                big = add;
        }
  
        return Math.min(ans, big - small);
    }
  
    // Driver function to test the above function
    public static void main(String[] args)
    {
        int arr[] = {4, 6};
        int n = arr.length;
        int k = 10;
        System.out.println("Maximum difference is "+
                            getMinDiff(arr, n, k));
    }
}
// This code is contributed by Prerna Saini

Python3

# Python 3 program to find the minimum
# possible difference between maximum 
# and minimum elements when we have to
# add / subtract every number by k
  
# Modifies the array by subtracting / 
# adding k to every element such that
# the difference between maximum and 
# minimum is minimized
def getMinDiff(arr, n, k):
  
    if (n == 1):
        return 0
  
    # Sort all elements
    arr.sort() 
  
    # Initialize result
    ans = arr[n-1] - arr[0
  
    # Handle corner elements
    small = arr[0] +
    big = arr[n-1] -
      
    if (small > big):
        small, big = big, small 
  
    # Traverse middle elements
    for i in range(1, n-1):
      
        subtract = arr[i] -
        add = arr[i] +
  
        # If both subtraction and addition
        # do not change diff
        if (subtract >= small or add <= big):
            continue
  
        # Either subtraction causes a smaller
        # number or addition causes a greater
        # number. Update small or big using
        # greedy approach (If big - subtract
        # causes smaller diff, update small
        # Else update big)
        if (big - subtract <= add - small):
            small = subtract 
        else:
            big = add 
      
  
    return min(ans, big - small) 
  
  
# Driver function
arr = [ 4, 6
n = len(arr) 
k = 10
  
print("Maximum difference is", getMinDiff(arr, n, k)) 
  
# This code is contributed by
# Smitha Dinesh Semwal

C#

// C# program to find the minimum 
// possible difference between 
// maximum and minimum elements
// when we have to add/subtract
// every number by k
using System; 
  
class GFG 
{
  
// Modifies the array by subtracting/adding
// k to every element such that the difference
// between maximum and minimum is minimized
static int getMinDiff(int[] arr, int n, int k)
{
    if (n == 1)
    return 0;
  
    // Sort all elements
    Array.Sort(arr);
  
    // Initialize result
    int ans = arr[n - 1] - arr[0];
  
    // Handle corner elements
    int small = arr[0] + k;
    int big = arr[n - 1] - k;
    int temp = 0;
      
    if (small > big)
    {
        temp = small;
        small = big;
        big = temp;
    }
  
    // Traverse middle elements
    for (int i = 1; i < n - 1; i ++)
    {
        int subtract = arr[i] - k;
        int add = arr[i] + k;
  
        // If both subtraction and 
        // addition do not change diff
        if (subtract >= small || add <= big)
            continue;
  
        // Either subtraction causes a smaller
        // number or addition causes a greater
        // number. Update small or big using
        // greedy approach (If big - subtract
        // causes smaller diff, update small
        // Else update big)
        if (big - subtract <= add - small)
            small = subtract;
        else
            big = add;
    }
  
    return Math.Min(ans, big - small);
}
  
// Driver Code
public static void Main()
{
    int[] arr = {4, 6};
    int n = arr.Length;
    int k = 10;
    Console.Write("Maximum difference is "+
                    getMinDiff(arr, n, k));
}
}
  
// This code is contributed 
// by ChitraNayal

PHP

<?php
// PHP program to find the minimum
// possible difference between 
// maximum and minimum elements when
// we have to add/subtract every 
// number by k
  
// Modifies the array by subtracting
// or adding k to every element such 
// that the difference between maximum 
// and minimum is minimized
function getMinDiff($arr, $n, $k)
{
    if ($n == 1)
    return 0;
  
    // Sort all elements
    sort($arr);
  
    // Initialize result
    $ans = $arr[$n - 1] - $arr[0];
  
    // Handle corner elements
    $small = $arr[0] + $k;
    $big = $arr[$n - 1] - $k;
    if ($small > $big)
    {
        $temp = $small;
        $small = $big;
        $big = $temp;
    }
      
    // Traverse middle elements
    for ($i = 1; $i < $n - 1; $i ++)
    {
        $subtract = $arr[$i] - $k;
        $add = $arr[$i] + $k;
  
        // If both subtraction and 
        // addition do not change diff
        if ($subtract >= $small || $add <= $big)
            continue;
  
        // Either subtraction causes a smaller
        // number or addition causes a greater
        // number. Update small or big using
        // greedy approach (If big - subtract
        // causes smaller diff, update small
        // Else update big)
        if ($big - $subtract <= $add - $small)
            $small = $subtract;
        else
            $big = $add;
    }
  
    return min($ans, $big - $small);
}
  
// Driver Code
$arr = array(4, 6);
$n = sizeof($arr);
$k = 10;
echo "Maximum difference is ";
echo getMinDiff($arr, $n, $k);
  
// This code is contributed by ihritik
?>


Output :

Maximum difference is 2

Time Complexity: O(n Log n)



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter