Pick m numbers from array of n numbers so their total differences are minimum

Question

There are n towers with variable number of floors in an ancient city. We have to build floors on them so that at least m out of n towers (n>=m) are of equal height. Write a function to calculate the minimum number of floors that need to be built for m floors to be of equal height.

Example: Given an array (1,5,4,2,1) each element representing the number of floors in that tower and m=3, the function should return 2 as we have to build 1 floor each to towers on index 0 & 4 so 3 towers will be of equal height. Function definition below

public Integer calcMinFloors(Integer[] towers, int m);

Answer 1

Updating the answer from @gnasher729:

Straightforward solution for n element array:

1. Sort in descending order: (5,4,2,1,1)
2. Loop over elements and for each element look ahead m-1 next elements. Sum the differences and save the minimum. Time complexity O(n*m)

Slightly more advanced solution:

1. Sort in descending order: (5,4,2,1,1)
2. Get first element (5), look ahead m-1 elements (4,2), count how many floors you need (1 + 3 = 4)and save the result as best and as current
3. Loop over array from element 2. for each element i calculate the value: current = current - (arr[i-1] - arr[i])*(m-1) + arr[i]-arr[i+m-1]. Save to best if it's smaller than it.

That should give time complexity O(n*log(n)) for sorting + O(n) for steps 2-3.

Answer 2

This problem is solvable is time O(NlogN) and constant space O(1), where N is the number of towers.

We have to make m towers of equal height such that we have to build minimum floors.

Important Observations

1. Because we are building minimum floors,rather than building floors on m towers and reach equal height, we will try to make m - 1 towers to be of equal height of a target tower.

2. The optimal solution lies in finding such m towers which have the minimum sum of heights difference.Let the solution be towers having following floors in ascending order:

m1 , m2 , m3 , ....... m floor

The optimal solution has the following property:

The sum of the differences is minimum:

(m - m1) + (m - m2) + (m - m3) + .....(m - (m-1))

Because only then we can say that we need to build minimum number of floors.

So it turns out we need to find set of m floors such that the difference of their heights from the floor with maximum height(within those m towers) is minimum.

Say we have array arr of length n, depicting the number of floors on each tower.First we sort the towers by their height.

Then we start finding the sum of the differences in following way.Say we are at index i in . We find the following sum:

arr[i + m - 1] - arr[i]
         +
arr[i + m - 2] - arr[i]
         +
arr[i + m - 3] - arr[i]
         +
arr[i + m - 4] - arr[i]
         .
         .
         .
arr[i + 1] - arr[i]

Lets call the sum s1. Now when we consider the next set of m towers , meaning towers from indices i + 1 to i + m, we do not need a loop to compute the sum of differences, it can simply be derived from following:

(m - 1)*arr[i + m] - s1 - ((m-1)*arr[i])

So using this simple mathematical technique, we only need a single for loop for this problem.

The pseudocode for the proposed algorithm is:

Sort the array arr of n towers.

Compute the sum of differences for first set of m towers.

sum = 0

for(i = 1 to m - 1)
{
  sum = sum + arr[i] - arr[0]
}

Now for the remaining set of m towers

previous_sum = sum, sum = 0, j = 1
minimum_sum = previous_sum
for(i = m to n - 1)
{

 sum = (m-1)*arr[i] - previous_sum - (m - 1)*arr[j - 1]
 increment j

 if( sum < minimum_sum )
 {
  minimum_sum = sum
 }

 previous_sum = sum
}

The answer is minimum_sum.