Equal elements in a Array

Question

Today I had Interview where I was asked one problem, and I couldnt even understand.

Problem:

Given one array 𝑎 consisting of 𝑛 integers.

Get at least 𝑘 equal elements in the array 𝑎.

While calculating, you can do below two operations

• Take one of the minimum elements of the array and increase its value by one (more formally, if the minimum value of 𝑎 is 𝑚𝑛 then you choose such index 𝑖 that 𝑎𝑖=𝑚𝑛 and set 𝑎𝑖:=𝑎𝑖+1);

• take one of the maximum elements of the array and decrease its value by one (more formally, if the maximum value of 𝑎 is 𝑚𝑥 then you choose such index 𝑖 that 𝑎𝑖=𝑚𝑥 and set 𝑎𝑖:=𝑎𝑖−1).

Calculate the minimum number of moves required to obtain at least 𝑘 equal elements in the array.

Can anyone help me to undestand, what's a actual problem is about so that I could write code ?

Answer 1

To answer your question directly, which is "Help me understand the problem":

For example, here's your array:

{1,2,5,7,8,3}

Now, you can do only those two operations:

1. Find the minimum element and increase it:

{2,2,5,7,8,3} // <-- increased 1

2. Decrease the maximum element:

{2,2,5,7,7,3} // <-- decreased 8

And the question now is: What is the minimum number of moves to make this array contain k identical numbers?

---

So if k = 3 and the array is like the above, then one of the solutions would be to run operation 1 three times:

1. Before any moves:

{1,2,5,7,8,3}

2. After first move:

{2,2,5,7,8,3} // <-- `1` changed to `2`

3. After second move:

{3,2,5,7,8,3} // <-- `2` changed to `3`

4. After third move:

{3,3,5,7,8,3} // <-- `2` changed to `3`

So the resulting array would be:

{3,3,5,7,8,3}

---

Do you understand the problem now?