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.

Output Format

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

Subtasks

Equal After And solution codechef

  • Subtask 1 (20 points):
    • 0Ai2550≤Ai≤255
    • Sum of NN over all test cases is at most 255255.
  • Subtask 2 (30 points):
    • Sum of NN over all test cases is at most 20002000.
  • Subtask 3 (50 points):
    • 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

Sample Output 1

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.

SOLUTION

Click here

Leave a Comment

Your email address will not be published.