# Equal by XORing | codechef solution

Problem

JJ has three integers $�$$�$, and $�$. He can apply the following operation on $�$:

• Select an integer $�$ such that $1\le �<�$ and set $�:=�\oplus �$. (Here, $\oplus$ denotes the bitwise XOR operation.)

JJ wants to make $�$ equal to $�$.
Determine the minimum number of operations required to do so. Print $-1$ if it is not possible.

### Input Format

• The first line contains a single integer $�$ — the number of test cases. Then the test cases follow.
• The first and only line of each test case contains three integers $�$$�$, and $�$ — the parameters mentioned in the statement.

### Output Format

For each test case, output the minimum number of operations required to make $�$ equal to $�$. Output $-1$ if it is not possible to do so.

### Constraints

• $1\le �\le 1000$
• $0\le �,�<{2}^{30}$
• $1\le �\le {2}^{30}$

• Subtask 1 (30 points): $�$ is a power of $2$.
• Subtask 2 (70 points): Original Constraints.

### Sample 1:

Input
Output
3
5 5 2
3 7 8
8 11 1

0
1
-1


### Explanation:

• Test Case $1$: $�$ is already equal to $�$. Hence we do not need to perform any operation.
• Test Case $2$: We can perform the operation with $�=4$ which is $<8$. Therefore $�=3\oplus 4=7$. Thus, only one operation is required.
• Test Case $3$: We can show that it is not possible to make $�$ equal to $�$.

### Sample 2:

Input
Output
2
24 27 3
4 5 1000

2
1

### Explanation:

Note that the above sample case belongs to subtask $2$.

• Test Case 1: We can first perform the operation with $�=1$ which is $<3$. Therefore $�=24\oplus 1=25$. Then we can perform the operation with $�=2$ which is $<3$. Therefore $�=25\oplus 2=27$. Therefore we can make $�$ equal to $�$ in $2$ operations. It can be shown that it is not possible to do this in less than $2$ operations.

Code(C++):-
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int a,b,c;
cin>>a>>b>>c;
int n=c;
int ans=a^b;
if(a==b){
cout<<0<<endl;
continue;
}
bool f=true;
int cnt=1;
int hlp=0;
int maxi=0;
for(int i=0;i<32;i++){
if(ans&(1<<i)){
maxi=pow(2,i);
}
}
if(maxi>=n){
cout<<-1<<endl;
continue;
}
for(int i=31;i>=0;i--){
if(ans&(1<<i)){
hlp=hlp|(1<<i);
}
if(hlp>=n){
hlp=0;
cnt++;
hlp=hlp|(1<<i);
}
}
cout<<cnt<<endl;

}
return 0;
}

Code(JAVA):-

import java.util.*;

import javax.lang.model.util.ElementScanner14;

import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef {
public static int gcf(int a, int b) {
if (b == 0)
return a;
return gcf(b, a % b);
}

public static int lcm(int a, int b) {
return (a * b) / gcf(a, b);
}
public static int highestsetbit(long n)
{
int count=0;
while(n>0)
{
count++;
n=n>>1;
}
return count;
}
public static void main(String[] args) throws java.lang.Exception {
Scanner input = new Scanner(System.in);
int test = input.nextInt();
while (test > 0) {
long a=input.nextLong();
long b=input.nextLong();
long n=input.nextLong();
long c=a^b;
int x=highestsetbit(c);
int y=highestsetbit(n);
long temp=(long)Math.pow(2,x-1);
if(c==0)
System.out.println(0);
else if(c<n)
System.out.println(1);
else if(temp>=n)
{
System.out.println(-1);
}
else if(n<=c)
{
System.out.println(2);
}
test--;
}
}
}