You are given a number (divisible by ) and an array . In one move, you can increase any of the array elements by one. Formally, you choose the index () and replace with . You can choose the same index multiple times for different moves.
Let's denote by , and the number of numbers from the array that have remainders , and when divided by the number , respectively. Let's say that the array has balanced remainders if , and are equal.
For example, if and , then the following sequence of moves is possible:
- initially , and , these values are not equal to each other. Let's increase , now the array ;
- , and , these values are not equal. Let's increase , now the array ;
- , and , these values are not equal. Let's increase , now the array ;
- , and , these values are equal to each other, which means that the array has balanced remainders.
Find the minimum number of moves needed to make the array have balanced remainders.
The first line contains one integer (). Then test cases follow.
The first line of each test case contains one integer () — the length of the array . It is guaranteed that the number is divisible by .
The next line contains integers ().
It is guaranteed that the sum of over all test cases does not exceed .
For each test case, output one integer — the minimum number of moves that must be made for the array to make it have balanced remainders.
4 6 0 2 5 5 4 8 6 2 0 2 1 0 0 9 7 1 3 4 2 10 3 9 6 6 0 1 2 3 4 5
3 1 3 0
The first test case is explained in the statements.
In the second test case, you need to make one move for .
The third test case you need to make three moves:
- the first move: ;
- the second move: ;
- the third move: .
In the fourth test case, the values , and initially equal to each other, so the array already has balanced remainders.
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.