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 \((0 \leq a[i] \leq 1)\)
Output:
Print \(T\) lines
Each line should contain the answer for that test case
Constraints :
\(1 \leq T \leq 10^3\)
\(1 \leq N \leq 10^5\)
\(0 \leq a[i] \leq 1\)
The sum of \(N\) over all test cases does not exceed \(10^5\)
1 6 1 1 0 0 1 0
1
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor