Array Cloning Technique solution codechef
You are given an arrayof integers. Initially there is only one copy of the given array. You can do operations of two types:
- Choose any array and clone it. After that there is one more copy of the chosen array.
- Swap two elements from any two copies (maybe in the same copy) on any positions.
InputThe input consists of multiple test cases. The first line contains a single integer ( ) — the number of test cases. Description of the test cases follows. The first line of each test case contains a single integer ( ) — the length of the array . The second line of each test case contains integers ( ) — the elements of the array . It is guaranteed that the sum of over all test cases does not exceed .
OutputFor each test case output a single integer — the minimal number of operations needed to create at least one copy where all elements are equal.
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
0 6 2 5 7 0
NoteIn the first test case all elements in the array are already equal, that’s why the answer is . In the second test case it is possible to create a copy of the given array. After that there will be two identical arrays: and After that we can swap elements in a way so all zeroes are in one array: and Now let’s create a copy of the first array: , and Let’s swap elements in the first two copies: , and . Finally, we made a copy where all elements are equal and made operations. It can be proven that no fewer operations are enough.