Pairwise Xors XORABC Codechef Solution
JJ gives Chef a number X and challenges Chef to come up with three distinct numbers A, B, and C such that: 0≤A,B,C<230; (A⊕B)+(B⊕C)+(C⊕A)=X. Help Chef come up with three such numbers or determine that no such tuple exists. Here, ⊕ denotes the bitwise XOR operation.
Input Format
- The first line contains a single integer T – the number of test cases. Then the test cases follow.
- The first and only line of each test case contains an integer X – the number mentioned in the problem statement.
Output Format
- For each test case, output three distinct numbers A, B and C (0≤A,B,C<230) such that (A⊕B)+(B⊕C)+(C⊕A)=X.
- If multiple such tuples exist, print any. If no such tuple exists, print −1.
Constraints
- 1≤T≤1000
- 1≤X<230
Sample Input 1
3
6
3
20
Sample Output 1
0 1 3
-1
3 11 1
Explanation
- Test Case 1: A=0,B=1,C=3 is a valid answer because (0⊕1)+(1⊕3)+(3⊕0)=1+2+3=6.
- Test Case 2: It can be proven that no tuple exists that satisfies the given conditions.
- Test Case 3: A=3,B=11,C=1 is a valid answer because (3⊕11)+(11⊕1)+(1⊕3)=8+10+2=20.
SOLUTION
Program: Pairwise Xors XORABC Codechef Solution in Python
for _ in range(int(input())):
n=int(input())
x=n & ~(n-1)
if(n&1 or n==x):
print("-1")
else:
print(x//2,n//2,(n-x)//2)
Program: Pairwise Xors XORABC Codechef Solution in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner in=new Scanner(System.in);
int t=in.nextInt();
while(t>0)
{
t--;
int n=in.nextInt();
int a=n&~(n-1);
int k=n&1;
if(n==a || k!=0)
System.out.println("-1");
else
System.out.println(a/2+" "+n/2+" "+(n-a)/2);
}
}
}
Program: Pairwise Xors XORABC Codechef Solution in C++
#include <iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--)
{
long long n;
cin>>n;
long long a=n & ~(n-1);
if(n&1 || n==a) cout<<-1<<endl;
else cout<< a/2 <<" "<<n/2<<" "<<(n-a)/2<<endl;
}
return 0;
}
Related: