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.
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