[Solution] Array Cloning Technique solution codeforces

Array Cloning Technique solution codeforces – You are given an array 𝑎a of 𝑛n integers. Initially there is only one copy of the given array.

You can do operations of two types:

  1. Choose any array and clone it. After that there is one more copy of the chosen array.
  2. Swap two elements from any two copies (maybe in the same copy) on any positions.

[Solution] Array Cloning Technique solution codeforces

You need to find the minimal number of operations needed to obtain a copy where all elements are equal.

Input

The input consists of multiple test cases. The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer 𝑛n (1𝑛1051≤n≤105) — the length of the array 𝑎a.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (109𝑎𝑖109−109≤ai≤109) — the elements of the array 𝑎a.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 105105.

Output

For each test case output a single integer — the minimal number of operations needed to create at least one copy where all elements are equal.

[Solution] Array Cloning Technique solution codeforces

Example
input

Copy
6
1
1789
6
0 1 3 3 7 0
2
-1000000000 1000000000
4
4 3 2 1
5
2 5 7 6 3
7
1 1 1 1 1 1 1
output

Copy
0
6
2
5
7
0

Array Cloning Technique solution codeforces

In the first test case all elements in the array are already equal, that’s why the answer is 00.

In the second test case it is possible to create a copy of the given array. After that there will be two identical arrays:

[ 0 1 3 3 7 0 ][ 0 1 3 3 7 0 ] and [ 0 1 3 3 7 0 ][ 0 1 3 3 7 0 ]

After that we can swap elements in a way so all zeroes are in one array:

[ 0 0⎯⎯ 0⎯⎯ 3 7 0 ][ 0 0_ 0_ 3 7 0 ] and [ 1⎯⎯ 1 3 3 7 3⎯⎯ ][ 1_ 1 3 3 7 3_ ]

Now let’s create a copy of the first array:

[ 0 0 0 3 7 0 ][ 0 0 0 3 7 0 ][ 0 0 0 3 7 0 ][ 0 0 0 3 7 0 ] and [ 1 1 3 3 7 3 ][ 1 1 3 3 7 3 ]

Let’s swap elements in the first two copies:

[ 0 0 0 0⎯⎯ 0⎯⎯ 0 ][ 0 0 0 0_ 0_ 0 ][ 3⎯⎯ 7⎯⎯ 0 3 7 0 ][ 3_ 7_ 0 3 7 0 ] and [ 1 1 3 3 7 3 ][ 1 1 3 3 7 3 ].

Finally, we made a copy where all elements are equal and made 66 operations.

It can be proven that no fewer operations are enough.

 

For Solution

Click here

Leave a Comment