Delhi boys love candies and have brought some to their school assembly on Christmas.
N boys are present on that day and each boy has a different number of candies(Ci) with him. But after seeing some boys (with lesser candies) sad, the Principal decides to put a smile on their faces by pooling all the candies in one big basket and distributing them equally among all. But after pooling all the candies, the boys who had more candies initially fear their loss and get sad. You, being the Santa, are to help the sad boys by adding some more candies to the big basket so that no one is sad.
You need to find the minimum number of additional candies required to keep everyone happy.
The first line of the input contains T representing the number of test cases.
Each test case contains an integer N representing the number of boys.
The next line contains N spaced integers Ci each representing the number of candies with the ith boy.
For each test case, output a single integer containing the minimum number of additional candies required.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 5 × 104
- 1 ≤ Ci ≤ 105
- Subtask #1[30 points] : 1 ≤ N ≤ 100
- Subtask #2[70 points] : Original constraints
Input: 2 3 1 1 3 2 1 1 Output: 4 0
Example case 1. By adding 4 candies, each boy would get 3 candies and be happy.
Example case 2. There is no need to add candies as everyone is already happy.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.