Subarray

2.8

6 votes
Basics of Input/Output, Bit Manipulation, Basic Programming, Input/Output, Basics of Bit Manipulation
Problem

Given a binary array. Find the minimum number of swap operations to be performed such that the Bitwise AND of any subarray of size > 1 is equal. If it can't be done, print 1. Swap can be defined as interchanging array values at any two indices i and j.

Input:

The first line contains T, the number of test cases

The first line of each test case contains N, the number of elements in the array

The second line of each test case contains N integers (0a[i]1)

Output:

Print T lines

Each line should contain the answer for that test case

Constraints :

1T103

1N105

0a[i]1

The sum of N over all test cases does not exceed 105

Sample Input
1 
6
1 1 0 0 1 0
Sample Output
1
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

We can swap indices 2 and 3. This way the array becomes 1 0 1 0 1 0. 
Now the Bitwise AND of every subarray of size >1 is equal to 0.
It can be shown that this is the best possible answer.

Editor Image

?