Problem Brief

Get Minimum Moves

Initially, all applications are deployed on n servers, with varying load handling capacities. The developers want to divide the n servers into clusters of cluster_size each such that the servers in each cluster have the same load-handling capacity. To achieve this, developers can recalibrate one or more servers. In one move, any server can be reconfigured to handle a lesser load than its current capacity, i.e., in one move capacity[i], can be changed to any integer value less than capacity[i].

Given the initial capacities of the servers, in an array, capacity, of size n, and an integer cluster_size, find the minimum number of moves required to divide the servers into clusters.

Function Description

Complete the function getMinimumMoves in the editor below.

getMinimumMoves has the following parameters:

int capacity[n]: the initial load-handling capacity of the servers
int cluster_size: the size of each cluster

Returns

int: minimum moves to divide the n servers into clusters as mentioned above

🍉 A supa huge thank-you to a wonderful friend for all the help! 🍊

1Example 1

Input

capacity = [4, 2, 4, 4, 7, 4], cluster_size = 3

Output

Explanation

At least 2 moves to get clusters of size 3 each..

2Example 2

Input

capacity = [1,2,2,3,4,5,5,6], cluster_size = 4

Output

Explanation

5 changes to get [1,1,1,1,2,2,2,2].

3Example 3

Input

capacity = [1,1,3,2], cluster_size = 2

Output

Explanation

1 change to get [1,1,2,2].

4Example 4

Input

capacity = [5, 4, 2, 7, 1, 1, 5, 3, 4, 7, 4, 3, 6, 2, 1, 7, 5, 7, 5, 6, 5, 2, 1, 1, 1, 3, 4, 1, 7, 3], cluster_size = 5

Output

Explanation

5 changes to get [1,1,1,1,1,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,7,7,7,7,7].

Constraints

Limits and guarantees your solution can rely on.

1 ≤ n ≤ 2 x 10^5
1 ≤ capacity[i] ≤ 10^9
1 ≤ cluster_size ≤ n
n is a multiple of cluster_size.