Mod Equality solution codechef

Mod Equality solution codechef


You are given NN non-negative integers A1,A2,,ANA1,A2,…,AN. You are allowed to perform following operation any number of times:

  • Choose any valid index ii (1iN1≤i≤N) and a positive integer M>0M>0 and replace AiAi with AimodMAimodM. That is, replace AiAi with its remainder when divided by MM, which is a value between 00 and M1M−1, inclusive.
  • MM does not need to be same between different operations.

Find the minimum number of operations to make all the array elements equal.

Note: Since the input and output are large, prefer using fast input-output methods.

Input Format

  • The first line contains an integer TT – the number of test cases. Then TT test cases follow.
  • The first line of each test case contains an integer NN – the size of array.
  • The second line contains NN integers A1,A2,,ANA1,A2,…,AN – the elements of the array.

Output Format

For each test, print one line containing an integer which denotes minimum number of operations performed to make all the elements equal.

Constraints

  • 1T1041≤T≤104
  • 1N1051≤N≤105
  • 0Ai21090≤Ai≤2⋅109
  • It is guaranteed that the sum of NN over all test cases does not exceed 106106.

Sample Input 1 

2
3
2 1 3
3
1 1 3

Sample Output 1 

3
1

Explanation

In first test case, we can make all the elements equal by following operations:

  • Take i=1i=1 and M=2M=2 and do A1:=A1mod2=0A1:=A1mod2=0.
  • Take i=2i=2 and M=1M=1 and do A2:=A2mod1=0A2:=A2mod1=0.
  • Take i=3i=3 and M=3M=3 and do A3:=A3mod3=0A3:=A3mod3=0.
    After these 33 operations we have all the elements equal to zero.

In second test case, we can perform following operation:

  • Choose i=3i=3 and M=2M=2 and do A3:=A3mod2=1A3:=A3mod2=1.
    After this operation all the elements are 11.

Leave a Comment