Friends and Candies

题意翻译

**【题目描述】** Polycarp 有 $n$ 个朋友，第 $i$ 个朋友有 $a_i$ 块糖果。Polycarp 希望他的每个朋友拥有的糖果数量相同，且他能选择任意朋友将他的糖果任意分配给其他朋友。求 Polycarp 最少需要选择几个朋友，将他们拥有的糖果重新分配就能达成目的。 **【输入格式】** 在输入的第一行为一个整数 $t$（$1 \le t \le {10}^4$），为数据组数。 接下来对于每组数据，第一行为一个整数 $n$（$2 \le n \le 2 \times {10}^5$），为朋友的数量；第二行有 $n$ 个整数 $a_1, a_2, \ldots , a_n$（$0 \le a_i \le {10}^4$），为每个朋友拥有的糖果数。 保证对于所有组数据 $\sum n \le 2 \times {10}^5$。 **【输出格式】** 对于每组数据，输出一个整数 $k$ 表示 Polycarp 最少需要选择的朋友数量。 如果不存在这样的 $k$，请输出 $-1$。

题目描述

Polycarp has $ n $ friends, the $ i $ -th of his friends has $ a_i $ candies. Polycarp's friends do not like when they have different numbers of candies. In other words they want all $ a_i $ to be the same. To solve this, Polycarp performs the following set of actions exactly once: - Polycarp chooses $ k $ ( $ 0 \le k \le n $ ) arbitrary friends (let's say he chooses friends with indices $ i_1, i_2, \ldots, i_k $ ); - Polycarp distributes their $ a_{i_1} + a_{i_2} + \ldots + a_{i_k} $ candies among all $ n $ friends. During distribution for each of $ a_{i_1} + a_{i_2} + \ldots + a_{i_k} $ candies he chooses new owner. That can be any of $ n $ friends. Note, that any candy can be given to the person, who has owned that candy before the distribution process. Note that the number $ k $ is not fixed in advance and can be arbitrary. Your task is to find the minimum value of $ k $ . For example, if $ n=4 $ and $ a=[4, 5, 2, 5] $ , then Polycarp could make the following distribution of the candies: - Polycarp chooses $ k=2 $ friends with indices $ i=[2, 4] $ and distributes $ a_2 + a_4 = 10 $ candies to make $ a=[4, 4, 4, 4] $ (two candies go to person $ 3 $ ). Note that in this example Polycarp cannot choose $ k=1 $ friend so that he can redistribute candies so that in the end all $ a_i $ are equal. For the data $ n $ and $ a $ , determine the minimum value $ k $ . With this value $ k $ , Polycarp should be able to select $ k $ friends and redistribute their candies so that everyone will end up with the same number of candies.

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ). Then $ t $ test cases follow. The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^4 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case output: - the minimum value of $ k $ , such that Polycarp can choose exactly $ k $ friends so that he can redistribute the candies in the desired way; - "-1" if no such value $ k $ exists.

输入输出样例

输入样例 #1

5
4
4 5 2 5
2
0 4
5
10 8 5 1 4
1
10000
7
1 1 1 1 1 1 1

输出样例 #1

2
1
-1
0
0