Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Zarin is a sadist. She loves to give problems to her close people.
Today she gives you an array consisting of n integers **a _{1}, a_{2},…,a_{n}**, and a positive integer

Now you have to do magic.

In a single magic, you can take any index **i** between **1** and **n** and increase **a _{i}** by

Let’s determine **x _{r} (0 ≤ r ≤ k − 1)** — the number of items consisting remainder

You have to modify the array in a way that **x _{0} = x_{1} = ⋯ = x_{k-1} = n/k**.

Now Zarin wants to know the minimum number of magics to satisfy the above requirement.

The first line of input contains two integers **n** and **k** **(1 ≤ n ≤ 2*10 ^{5},1 ≤ k ≤ n)**.

The second line of input contains **n** integers **a _{1},a_{2},…,a_{n} (0 ≤ a_{i} ≤ 10^{9})**.

Print a single integer — the minimum number of moves required to satisfy the following condition: for each remainder from **0** to **k−1**, the number of elements of the array having this remainder equals **n/k**.

Input | Output |
---|---|

6 3 6 10 12 3 0 2 | 3 |

55% Solution Ratio

agtxdyEarliest,

EgorKulikovFastest, 0.0s

Shaad221BLightest, 524 kB

tmwilliamlin168Shortest, 527B

Login to submit