# Bitwise Blend Solution Codechef

## Bitwise Blend Solution Codechef

Chef loves bitwise operations. So, he creates the following problem but needs your help to solve it.

Chef calls a sequence of integers A1,A2,…,A `tasty` if it satisfies the following condition:

• parity(Ai&Ai+1)≠parity(Ai|Ai+1) for 1≤i<N.

Chef gives you a sequence A1,A2,…,AN. You may perform the following operation on the sequence any number of times (possibly 0):

• Choose 2 indices ii and jj (1≤i,j≤n ; i≠j) and change Ai to Ai⊕Aj.

Chef is asking you to make the sequence `tasty` using the minimum number of operations, or report that it is impossible.

As a friendly reminder,

Input Format

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N.
• The second line contains N space-separated integers A1,A2,…,AN.

Output Format

For each test case:

• If it is impossible to convert the given sequence into a `tasty` sequence using the given operations, print a single line containing the integer −1.
• Otherwise, first, print a line containing a single integer M the minimum number of operations you have to perform.
• Then, print M lines describing these operations in the order in which you want to perform them. For each kk (1≤k≤M), the kk-th of these lines should contain two space-separated integers i and j (1≤i,j≤n ; i≠j) the indices on which the k-th operation is performed.

If there are multiple solutions, you may find any one of them.

Constraints

• 1≤T≤3⋅103
• 2≤N≤105
• 0≤Ai<230 for each valid i
• The sum of N over all test cases does not exceed 2⋅105

Subtask #1 (100 points): Original constraints

Sample Input 1

``````2
2
0 0
3
6 16 69``````

Sample Output 1

``````-1
1
1 3``````

Explanation

Test case 1: It is impossible to make A `tasty` using the given operations.

Test case 2: We can choose i=1 and j=3 and apply the operation which converts A into [67,16,69] which is `tasty`.

### SOLUTION

Program: Bitwise Blend Solution in Python

``````for _ in range(int(input())):
l=int(input())
seq=[int(i)%2 for i in input().split()]
if not any(seq):
print(-1)
else:
count=[[],[]]
k=0
for i in range(l):
count[k%2].append(i)
if i<l-1 and seq[i]==seq[i+1]:
k+=1
min=count if len(count)<=len(count) else count
print(len(min))
for i in min:
seq[i]=-1
print(i+1,1+seq.index(1))``````

Program: Bitwise Blend Solution in C++

``````#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
long long int a[n];
int flag=0;
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]%2!=0)
flag=1;
}
if(flag==0)
cout<<"-1"<<endl;
else{
int count1=0,count2=0;
for(int i=0;i<n;i++){
if(i%2==0)
if(a[i]%2)
count1++;
else
count2++;
else
if(a[i]%2)
count2++;
else
count1++;
}
int m=min(count1,count2);
if(count2==m){
cout<<m<<endl;
int temp=0;
for(int i=0;i<n;i=i+2)
if(a[i]%2){
temp=i;
break;
}
for(int i=0;i<n;i++)
if(i%2==0){
if(a[i]%2==0)
cout<<i+1<<" "<<temp+1<<endl;
}
else{
if(a[i]%2)
cout<<i+1<<" "<<temp+1<<endl;
}
}
else{
cout<<m<<endl;
int temp=0;
for(int i=1;i<n;i=i+2)
if(a[i]%2){
temp=i;
break;
}
for(int i=0;i<n;i++)
if(i%2==0){
if(a[i]%2)
cout<<i+1<<" "<<temp+1<<endl;
}
else{
if(a[i]%2==0)
cout<<i+1<<" "<<temp+1<<endl;
}

}

}
}
return 0;
}``````

Program: Bitwise Blend Solution in Java

``````import java.util.*;
import java.io.*;
class Codechef {
public static void main(String[] args) throws java.lang.Exception {

int t = sc.nextInt();
while (t-- > 0)
{
int n=sc.nextInt();
int arr[]= new int[n];int count=0;int s=1;int odd1=-1,odd2=-1;
ArrayList<Integer> l1 = new ArrayList<Integer>();
ArrayList<Integer> l2 = new ArrayList<Integer>();
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
if(arr[i]%2!=0)
{count=count+1;
if(i%2==0&&odd1==-1)
{
odd1=i+1;
}
if(i%2!=0&&odd2==-1)
{
odd2=i+1;
}
}
if(arr[i]%2==s)
{

}
else
{

}
if(s==0)
{
s=1;
}
else
{
s=0;
}

}
int a=l1.size();
int b=l2.size();
if(count==0)
{
System.out.println(-1);
}
else if(a==0||b==0)
{
System.out.println(0);
}
else if(a<b)
{
System.out.println(a);
for (int i = 0; i < l1.size(); i++)
{

System.out.println((l1.get(i)+1)+" "+odd1);

}
}
else
{
System.out.println(b);
for (int i = 0; i < l2.size(); i++)
{
System.out.println((l2.get(i)+1)+" "+odd2);
}
}
}
}
}``````