7219: CodeChef EQDIFFER - Equal Difference
[Creator : ]
Description
You are given an array of $N$ integers.
Find the minimum number of integers you need to delete from the array such that the absolute difference between each pair of integers in the remaining array will become equal.
给定一个包含有 $N$ 个整数的数组。找出最少可以从数组中删除的整数的数量，使得数组中每对整数的绝对值之差相等。
Find the minimum number of integers you need to delete from the array such that the absolute difference between each pair of integers in the remaining array will become equal.
给定一个包含有 $N$ 个整数的数组。找出最少可以从数组中删除的整数的数量，使得数组中每对整数的绝对值之差相等。
Input
The first line of input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains an integer $N$.
The second line of each test case contains $N$ space-separated integers $A_1, A_2, \dots, A_N$.
The first line of each test case contains an integer $N$.
The second line of each test case contains $N$ space-separated integers $A_1, A_2, \dots, A_N$.
Output
For each test case, print a single line containing one integer - the minimum number of integers to be deleted to satisfy the given condition.
Constraints
$1≤T≤10^4$
$1 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9$
Sum of $N$ over all test cases does not exceed $5 \cdot 10^5$.
$1 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9$
Sum of $N$ over all test cases does not exceed $5 \cdot 10^5$.
Sample 1 Input
3
2
1 2
5
2 5 1 2 2
4
1 2 1 2
Sample 1 Output
0
2
2
Test case 1: There is only one pair of integers and the absolute difference between them is $|A_1 - A_2| = |1 - 2| = 1$. So there is no need to delete any integer from the given array.
Test case 2: If the integers 1 and 5 are deleted, the array A becomes [2, 2, 2] and the absolute difference between each pair of integers is 0. There is no possible way to delete less than two integers to satisfy the given condition.
Test case 2: If the integers 1 and 5 are deleted, the array A becomes [2, 2, 2] and the absolute difference between each pair of integers is 0. There is no possible way to delete less than two integers to satisfy the given condition.