Pairwise Xors XORABC Codechef Solution

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:

Leave a Comment

1 + twelve =