FastPrep
Problem · Array

Get Minimum Moves

● MediumOA

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:

  1. int capacity[n]: the initial load-handling capacity of the servers
  2. 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! 🍊

Examples
01 · Example 1
capacity = [4, 2, 4, 4, 7, 4]
cluster_size = 3
return = 2
Example 1 illustration
At least 2 moves to get clusters of size 3 each..
02 · Example 2
capacity = [1,2,2,3,4,5,5,6]
cluster_size = 4
return = 5
5 changes to get [1,1,1,1,2,2,2,2].
03 · Example 3
capacity = [1,1,3,2]
cluster_size = 2
return = 1
1 change to get [1,1,2,2].
04 · Example 4
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
return = 5
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
  • 1 ≤ n ≤ 2 x 10^5
  • 1 ≤ capacity[i] ≤ 10^9
  • 1 ≤ cluster_size ≤ n
  • n is a multiple of cluster_size.
drafts saved locally
public int getMinimumMoves(int[] capacity, int clusterSize) {
  // write your code here
}
capacity[4, 2, 4, 4, 7, 4]
cluster_size3
expected2
sign in to submit