Array Cloning Technique solution codechef

Array Cloning Technique solution codechef

 
You are given an array aa of nn 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.
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 tt (1t1041≤t≤104) — the number of test cases. Description of the test cases follows. The first line of each test case contains a single integer nn (1n1051≤n≤105) — the length of the array aa. The second line of each test case contains nn integers a1,a2,,ana1,a2,…,an (109ai109−109≤ai≤109) — the elements of the array aa. It is guaranteed that the sum of nn 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.
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
Note
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.

Leave a Comment