14

I was going through some interview questions, I saw this one

You are given the height of n towers and value k. You have to either increase or decrease the height of every tower by k. You need to minimize the difference between the height of the longest and the shortest tower and output this difference.

I think the answer will be (maxheight-k) - (minheight + k). I have tried on some test cases it is running fine.

But I am not sure, I think I am missing something, Am I ?

6
  • 1
    You didn't take to account the case then shortest tower became higher than another in the middle. Same for highest. Did you?
    – SouXin
    Aug 26, 2015 at 18:24
  • I'm not sure this question is actually testing any programming skill persay, but rather just tests your though process. I'm not convinced it's programming related.
    – ryanyuyu
    Aug 26, 2015 at 18:26
  • @SouXin: yaa that true. My bad. Do you have idea of some logic to do this ? Aug 26, 2015 at 18:30
  • You need decrease or increase height until difference between each towers will be less than k. I guess. ;) Just try 3 towers with h: 10, 3, 8 and k = 2. According your logic diff = 3 but in reality is 1. Resulted towers could be: 6, 5, 6
    – SouXin
    Aug 26, 2015 at 18:33
  • 2
    @SouXin : Well, It was not written explicitely in question.but from the language I thought that we can either increase or decrease the hieght by K only once. Correct me If I am wrong ? Aug 26, 2015 at 18:53

9 Answers 9

17

m7thon's answer explains the problem with your solution, so I'll just explain how you can actually solve this . . .

The big thing to observe is that for any given tower, if you choose to increase its height from hi to hi + k, then you might as well increase the height of all shorter towers: that won't affect the maximum (because if hj < hi, then hj + k < hi + k), and may help by increasing the minimum. Conversely, if you choose to decrease the height of a tower from hi to hi − k, then you might as well decrease the heights of all taller towers.

So while there are 2n possible ways to choose which towers should be increased vs. decreased, we can actually ignore most of these. Some tower will be the tallest tower that we increase the height of; for all shorter towers, we will increase their height as well, and for all taller towers, we will decrease their height. So there are only n interesting ways to choose which towers should be increased vs. decreased: one for each tower's chance to be the tallest tower that we increase the height of.

[Pedantic note #1: You may notice that it's also valid to decrease the heights of all towers, in which case there's no such tower. But that's equivalent to increasing the heights of all towers — whether we add k to every height or subtract k from every height, either way we're not actually changing the max-minus-min.]

[Pedantic note #2: I've only mentioned "shorter towers" and "taller towers", but it's also possible that multiple towers have the same initial height. But this case isn't really important, because we might as well increase them all or decrease them all — there's no point increasing some and decreasing others. So the approach described here still works fine.]

So, let's start by sorting the original heights and numbering them in increasing order, so that h1 is the original height of the originally-shortest tower and hn is the original height of the originally-tallest tower.

For each i, try the possibility that the ith-shortest tower is the tallest tower that we increase the height of; that is, try the possibility that we increase h1 through hi and decrease hi+1 through hn. There are two groups of cases:

  • If i < n, then the final height of the finally-shortest tower is min(h1 + khi+1 − k), and the final height of the finally-tallest tower is max(hi + khn − k). The final difference in this case is the latter minus the former.
  • If i = n, then we've increased the heights of all towers equally, so the final difference is just hn − h1.

We then take the least difference from all n of these possibilities.

Here's a Java method that implements this (assuming int-valued heights; note that hi is arr[i-1] and hi+1 is arr[i]):

private static int doIt(final int[] arr, final int k) {
    java.util.Arrays.sort(arr);
    final int n = arr.length;
    int result = arr[n - 1] - arr[0];
    for (int i = 1; i < n; ++i) {
        final int min = Math.min(arr[0] + k, arr[i] - k);
        final int max = Math.max(arr[n - 1] - k, arr[i - 1] + k);
        result = Math.min(result, max - min);
    }
    return result;
}

Note that I've pulled the i = n case before the loop, for convenience.

5

Lets say you have three towers of heights 1, 4 and 7, and k = 3. According to your reasoning the optimal minimum difference is (7 - 3) - (1 + 3) = 0. But what do you do with the tower of height 4? You either need to increase or decrease this, so the minimum difference you can achieve is in fact 3 in this example.

Even if you are allowed to keep a tower at its height, then the example 1, 5, 7 will disprove your hypothesis.

I know this does not solve the actual minimization problem, but it does show that it is not as simple as you thought. I hope this answers your question "Am I missing something?".

4

I assume this came from gfg.

The answer of @ruakh is perhaps the best I've found online, it'll work for most cases, but for the practice problem on gfg, there are a few cases which can cause the minimum to go below 0, and the question doesn't allow any height to be < 0.

So for that, you'll need an additional check, and the rest of it is pretty much entirely inspired from ruakh's answer

class Solution {
    int getMinDiff(int[] arr, int n, int k) {
        Arrays.sort(arr);
        int ans = arr[n-1] - arr[0];
        int smallest = arr[0] + k, largest = arr[n-1]-k;
        for(int i = 0; i < n-1; i++){
            int min = Math.min(smallest, arr[i+1]-k);
            int max = Math.max(largest, arr[i]+k);
            if(min < 0) continue;
            ans = Math.min(ans, max-min);
        }
        return ans;
    }
}

I also went in for 0-based indexing for the heights to make it more obvious, but maybe that's subjective.

Edit: One case where the < 0 check is important, is when the array is 8 1 5 4 7 5 7 9 4 6 and k is 5. The expected answer for this is 8, without the < 0 check, you'd get 7.

0

A bit late here. Already these guys have explained you the problem and given you the solution. However, I have prepared this code myself. The code I prepared is not the best code that you should follow but gives a clear understanding of what can be done to achieve this using brute-force.

set = list(map(int, input().split()))
k = int(input())
min = 999999999

for index in range(2**len(set)):

    binary = []      //probably should have used integer to binary fuction here
    while index != 0:
        remainder = index % 2
        index //= 2
        binary.append(remainder)
    while len(binary) != len(set):
        binary.append(0)
    binary.reverse()

    separateset = []
    flag = 0
    for i in range(len(binary)):
        if binary[i] == 0:
            separateset.append(set[i]+k)
        elif binary[i] == 1 and set[i]-k >= 0:
            separateset.append(set[i]-k)
        else:
            flag = 1
            break

    if flag == 0:
        separateset.sort()
        if min > separateset[-1] - separateset[0]:
            min = separateset[-1] - separateset[0]

print(min)

This is achieved by identifying all the possible subsets of the set variable but with just some modifications. If the digit is 0, the value at that i (index not the index in the for loop) in the set is added with k otherwise if the digit is 1 and set[i]-k >= 0, the value at that index in the set is subtracted by k (Now you can add or subtract k vice-versa, it doesn't matter until you get all possible combinations of +k and -k). set[i]-k >= 0 is to be followed because a negative height wouldn't make sense and if that happens, flag becomes 1 and breaks. But if the flag is 0, it means that all the heights are positive and then the separatesort is sorted and then min stores the difference between the largest and shortest tower. This min ultimately has the minimum of all the differences.

0

Step 1 :

Decrease all the heights by 'k' and sort them in non-decreasing order.

Step 2 :

We need to increase some subset of heights by '2 * k' (as they were decreased by 'k' in step1, so, to effectively increase their heights by 'k' we need to add '2*k') .

Step 3 :

Clearly if we increase the 'i'th height without increasing the 'i-1'th then, it will not be useful as the minimum is still the same and maximum may also increase !

Step 4 :

Consider all prefixes with '2*k' added to each element of the prefix . Then calculate and update the (max - min) value.

0

Let me know which scenario am I missing here,

class Solution:
    def getMinDiff(self, arr, n, k):
        for i in range(n):
            if arr[i] < k: arr[i] += k
            else: arr[i] -= k
        result = max(arr) - min(arr)
        print('NewArr: {}\nresult: {}'.format(arr, result))
        return result
0

C++ code :

int getMinDiff(int arr[], int n, int k) {
// code here
sort(arr , arr+n);
int result = arr[n - 1] - arr[0];
for (int i = 1; i < n; ++i) {
    int min_ = min(arr[0] + k, arr[i] - k);
    int max_ = max(arr[n - 1] - k, arr[i - 1] + k);
    result = min(result, max_ - min_);
}
return result;
}
1
  • As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.
    – Community Bot
    Apr 9, 2022 at 0:11
-1

First you are gonna need to find average height of the towers. lets say heights are 3, 7, 17, 25, 45 and k = 5 the average will be = ( 3 + 7 + 17 + 25 + 45 ) / 5 = 97 / 5 = 19.4

Now we will try to make every building closer to average height.

for 3 height tower we have to add 5 three times making height = 3 + (3*5) = 18 (18 is closer than 23) close to average.

for 7 height we will add 5 two times = 7 + (2 *5) = 17 (17 is closer than 22)

Similarly 25 will become 25 - 5 = 20 and 45 will become 45 - (5 *5) = 20

your height will becomes 18, 17, 17, 20, 20

2
  • 1
    The solution is wrong because you can increase/decrease by k only once. We can't increase by 2*k or more. Jul 1, 2016 at 15:57
  • 1
    Even if we could increase/decrease each tower's height more than once, this answer would still be wrong. Suppose the heights are [32, 48] and k is 5. This answer suggests that we bring the heights as close as possible to 40, meaning [42, 38], giving a result of 4; but in fact, you can get a result of 1 (e.g. with [47, 48]).
    – ruakh
    Aug 2, 2020 at 16:25
-2

This approach works on GfG practice, Problem link: https://practice.geeksforgeeks.org/problems/minimize-the-heights/0/

Approach :

  • Find max, min element from the array. O(n). Take the average, avg = (max_element + min_element)/2.
  • Iterate over the array again, and for each element, check if it is less than avg or greater.
  • If the current element arr[i] is less than avg, then add "k" to a[i], i.e a[i] = a[i] + k.
  • If the current element arr[i] is greater than or equal to avg, then subtract k from a[i], i.e a[i] = a[i] - k;
  • Find out the minimum and maximum element again from the modified array.
  • Return the min(max1-min1, max2-min2), where (max1, min1) = max and min elements initially before the array was modified, and (max2, min2) are the max and min elements after doing modification.

Entire Code can be found here: https://ide.geeksforgeeks.org/56qHOM0EOA

3
  • This doesn't give the best result in all cases. Suppose the heights are [20, 24, 25, 29] and k is 4. Then avg = (29 + 20) / 2 = 24.5, so the modified array is [24, 28, 21, 25], giving a result of 28 - 21 = 7; but you can get a better result, namely 5, with either [24, 20, 21, 25] or [24, 28, 29, 25].
    – ruakh
    Aug 2, 2020 at 16:52
  • Did you run the code, which is present at the link mentioned in my answer? That code is producing the output as 5, and now I have printed the array too, [24, 20, 21, 25], this is the array that I'm getting. Please note. I am using int, not float, and I am adding "k" to the elements that are lesser than avg, and subtracting k from the elements which are either greater or equal to avg. Aug 3, 2020 at 19:03
  • Re: "Did you run the code, which is present at the link mentioned in my answer?": No, I just went from the algorithm description, which doesn't mention rounding the average downward. But the code has the same problem; for example, if the heights are [40, 48, 50, 58] and k is 8, the code gives 14 instead of 10.
    – ruakh
    Aug 3, 2020 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.