Equal After And solution codechef

Equal After And  solution codechef

You are given an array A=[A1,A2,,AN]A=[A1,A2,…,AN], consisting of NN integers. In one move, you can take two adjacent numbers AiAi and Ai+1Ai+1, delete them, and then insert the number AiAi+1Ai∧Ai+1 at the deleted position. Here,  denotes bitwise AND. Note that after this operation, the length of the array decreases by one.

Formally, as long as |A|>1|A|>1 (where |A||A| denotes the current length of AA), you can pick an index 1i<|A|1≤i<|A| and transform AA into [A1,A2,,Ai1,AiAi+1,Ai+2,,A|A|][A1,A2,…,Ai−1,Ai∧Ai+1,Ai+2,…,A|A|].

Find the minimum number of moves required to make all numbers in the resulting array equal.

Input Format

• The first line of input contains an integer TT — the number of test cases you need to solve.
• The first line of each test case contains one integer NN, the size of the array.
• The second line of each test case contains NN space-separated integers A1,,ANA1,…,AN — the elements of the array AA.

Equal After And solution codechef

For each test case, output on a new line the minimum number of moves required to make all numbers equal.

Constraints

• 1T1061≤T≤106
• 2N1062≤N≤106
• Sum of NN over all test cases is at most 106106.
• 0Ai<2300≤Ai<230

Equal After And solution codechef

• 0Ai2550≤Ai≤255
• Sum of NN over all test cases is at most 255255.
• Sum of NN over all test cases is at most 20002000.
• Original constraints.

Sample Input 1

4
4
0 0 0 1
2
1 1
6
1 2 3 4 5 6
4
2 28 3 22


Equal After And solution codechef

1
0
4
3


Explanation

Test case 11: Choose i=3i=3 to make the array [0,0,01]=[0,0,0][0,0,0∧1]=[0,0,0].

Test case 22: All elements of the array are already equal.

Test case 33: One possible sequence of moves is as follows:

• Choose i=1i=1, making the array [12,3,4,5,6]=[0,3,4,5,6][1∧2,3,4,5,6]=[0,3,4,5,6]
• Choose i=2i=2, making the array [0,0,5,6][0,0,5,6]
• Choose i=3i=3, making the array [0,0,4][0,0,4]
• Choose i=2i=2, making the array [0,0][0,0]

It can be verified that in this case, making every element equal using 33 or fewer moves is impossible.