Equal Difference solution codechef- You are given an array of NN 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.

Equal Difference solution codechef

You are given an array of NN 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.

Input Format Equal Difference solution codechef

  • The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains an integer NN.
  • The second line of each test case contains NN space-separated integrs A1,A2,,ANA1,A2,…,AN.

Output Format

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

  • 1T1041≤T≤104
  • 1N1051≤N≤105
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test cases does not exceed 51055⋅105.

Sample Input 1 

3
2
1 2
5
2 5 1 2 2
4
1 2 1 2

Sample Output 1  Equal Difference solution codechef

0
2
2

Explanation

Test case 11: There is only one pair of integers and the absolute difference between them is |A1A2|=|12|=1|A1−A2|=|1−2|=1. So there is no need to delete any integer from the given array.

Test case 22: If the integers 11 and 55 are deleted, the array A becomes [2,2,2][2,2,2] and the absolute difference between each pair of integers is 00. There is no possible way to delete less than two integers to satisfy the given condition.