Practice on Toph

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


By dhruba_1603088 · Limits 1s, 256 MB

Zarin is a sadist. She loves to give problems to her close people.
Today she gives you an array consisting of n integers a1, a2,…,an, and a positive integer k.
She tells you that k is a divisor of n always.

Now you have to do magic.

In a single magic, you can take any index i between 1 and n and increase ai by 1.

Let's determine xr (0 ≤ r ≤ k − 1) — the number of items consisting remainder r when divided by k.
For each remainder, let's find the number of corresponding items in a with that remainder.

You have to modify the array in a way that x0 = x1 = ⋯ = xk-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*105,1 ≤ k ≤ n).

The second line of input contains n integers a1,a2,…,an (0 ≤ ai ≤ 109).


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.


6 3
6 10 12 3 0 2



65% Solution Ratio

agtxdyEarliest, Jan '20

TurinhstuFastest, 0.0s

Shaad221BLightest, 524 kB

omar24Shortest, 493B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.