Select m numbers from an array of n numbers so that their total differences are minimal

Question

In the ancient city there are Russian towers with a variable number of floors. We must build floors on them so that at least m of n towers (n> = m) are of the same height. Write a function to calculate the minimum number of floors that must be built so that m floors are the same height.

Example: for an array (1,5,4,2,1,1) each element representing the number of floors in this tower and m = 3, the function should return 2, since we must build 1 floor of each tower at index 0 and 4, therefore 3 towers will be of equal height. Function definition below

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

Answer 1

Update answer from @ gnasher729:

Direct solution for an array of n elements:

• Sort Descending: (5,4,2,1,1)
• Iterate over the elements and for each element look forward m-1 following elements. Summarize the differences and keep the minimum. Time complexity O(n*m)

A slightly more advanced solution:

• Sort Descending: (5,4,2,1,1)
• Get the first element (5) , look ahead m-1 elements (4,2) , calculate how many floors you need (1 + 3 = 4) and save the result as best and as current
• End the 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 the best if it is smaller.

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

Answer 2

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

We must make the towers equal to m equal to the height so that we build the minimum floors.

Important Observations

1 . Since we are building the minimum floors, and not building floors on the m towers and reaching equal heights, we will try to make m - 1 towers of the same height as the target towers.

2 . The optimal solution is to find such towers m that have the minimum sum of the height difference. Let this solution be towers having the following floors in ascending order :

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

The optimal solution has the following property:

The sum of the differences is minimal :

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

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

. Thus, we need to find many m floors in such a way that the difference between their heights and the floor with the maximum height (within these m towers) is minimal .

Let's say we have an arr array of length n, representing the number of floors on each tower. First we sort towers by height.

Then we start to find the sum of differences as follows. So, we are in index i in. Find the following amount:

 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 name the sum s1 . Now, when we consider the following set of towers m , which means towers from indices i + 1 to i + m , we do not need a cycle to calculate the sum of the differences, it can simply be derived from the following :

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

Thus, using this simple mathematical technique, we need only one loop for this problem.

Pseudocode for the proposed algorithm:

 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. 

Answer 3

You sort by height in ascending or descending order, and the rest are trivial.