Arrays: Minimize the maximum difference between the heights

Problem Statement:

You are given an array that represents the height of the towers.

You are also given a value “k”. You need to either increase or decrease the height of every tower by “k”.

Your task is to minimize the difference between the heights of the longest and the shortest tower.

Example:

Input array: {1, 5, 15, 10}

k = 3

Output = 8

So here you need to add or subtract 3 with all the elements in the array.

This is a minimization problem, so the solution should be an optimal.

So how did we arrive at this solution?

So what we did is

Add 3 to 1 => 3 + 1 = 4

Add 3 to 5 => 3 + 5 = 8

Subtract 3 from 15 => 15 – 3 = 12

Subtract 3 from 10 => 10 – 3 = 7

Resultant array will be {4, 8, 12, 7}

Now our task is to find the minimum difference between the longest and shortest tower

Here the longest tower is 12 and shortest is 4, the difference is 8

We can solve this problem in number of different ways.

Some of them discussed here are:

1. Brute Force Method

2. Optimized Method.

1. Brute Force Method

For brute force we consider below array of size 3.

Input array: {1, 15, 10}

k = 6

In brute force technique we go through all the possible combinations.

For the above array of 3 elements we get 2^n i.e 2^3 = 8 combinations as shown below:

{1+k, 15+k, 10+k} => {1+6, 15+6, 10+6} => {7, 21, 16} => Maxdiff 14

{1+k, 15+k, 10-k} => {1+6, 15+6, 10-6} => {7, 21, 4} => Max_diff 17

{1+k, 15-k, 10+k} => {1+6, 15-6, 10+6} => {7, 9, 16} => Max_diff 9

{1+k, 15-k, 10-k} => {1+6, 15-6, 10-6} => {7, 9, 4 } => Max_diff 5 <- answer

{1-k, 15+k, 10+k} => {1-6, 15+6, 10+6} => {-5, 21, 16} => Invalid, as height cannot be -ve

{1-k, 15-k, 10+k} => {1-6, 15-6, 10+6} => {-5, 9, 10}

{1-k, 15-k, 10-k} => {1-6, 15-6, 10-6} => {-5, 9, 4}

{1-k, 15+k, 10-k} => {1-6, 15+6, 10-6} => {-5, 21, 4}

So the solution is 5. As the max diff between the smaller and larger tower is 5.

 

1. Sort the given array.
2. Set the diff to the difference between the least element of the array and the first element of an array.
3. Set minimum to the first element of array + k and maximum to last element – k of the array.
4. Traverse the array from i=1 to i<n-1(one less than the length of the array).

1. Set difference to arr[i]-k.
2. Set sum to arr[i]+k.
3. Check if the difference is greater than equal to minimum or sum is less than or equal to maximum.
1. If true, then continue and skip this traversal.
4. Check if maximum-difference is less than or equal to sum-minimum.
1. If true, then update minimum to difference.
5. Else set the maximum to sum.

5. Return the minimum between the diff and maximum-minimum.

2. Optimized Method.

In this method, the time complexity will be reduced to O(nlogn)
1. Sort the array into ascending order.
2. As the initial result, take the difference between the first and the last element of the array
3. Now, take 2 variables small and big, that will add k to arr[0] and subtract k to arr[n-1]
4. Now traverse all the elements of the array.
1. take 2 variables sub and sum, that will subtract k and add k to the element at the index i.
2. If the difference is greater than the small variable and sum is smaller than the big variable continue to next index. Because in this case the smallest element is still hold by the variable small and larger variable is hold by big variable.
3. Else change the big and small variable appropriately.
5. After the end of traversal, return the min of the initial result and (big – small) value.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;  

int get_min_diff(int arr[], int n, int k) 
{ 
    sort(arr, arr+n); 
  
    int initial_result = arr[n-1] - arr[0]; 
  
    int small = arr[0] + k; 
    int big = arr[n-1] - k; 

    if (small > big) 
       swap(small, big); 
  
    for (int i = 1; i < n-1; i ++) 
    { 
        int sub = arr[i] - k; 
        int add = arr[i] + k; 
         
        // it means, still the small and big are in the correct position
        if (sub >= small || add <= big) 
            continue; 
         
        // if not, update the small and big value accordingly
        if (big - sub <= add - small) 
            small = sub; 
        else
            big = add; 
    } 
  
    return  min(initial_result, big - small); 
} 
  
int main() 
{ 
    int arr[] = {1, 15, 10}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int k = 6; 

    cout << "\nMaximum difference is "
        << get_min_diff(arr, n, k); 
    return 0; 
}

Output:

Maximum difference is 5
Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *