PROBLEM LINK:
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY:
cakewalk, SIMPLE.
PROBLEM:
In this problem, given an input integer N we need to find two integer A,b such that A ^ B = N where ‘^’ represnts XOR opration. But we also need to take care of some conditions that 1<=A<=B<=N and A must be minimum. If no such pair exsist then just print -1
EXPLANATION:
Here is the simple solution to this problem that we can simply use a brute force approach with time complexity of O(N) for each test case. Let me tell you one property of XOR which will help us to solve this problem. If X^N = Y where X and Y are any positive integers, we can also say that X^Y = N. Not to get in any confusion let’s implement this logic so, first we take 2 variables A and B assigning a value 0.
Before doing any implementation let me remind you the first condition of this problem that A should be minimum and greater than 1 so, what if we start a loop i=1 to N.In this loop, we need to check a simple condition that if i ^ N>=i and i ^ N<=N then A=i, B=i ^ N and we jump out of the loop. So for minimum A and A<=B<=N will be found. If we XOR A and B we will get N. Now we think about if the pair doesn’t exist then? After the loop, we will check that if A==0 and B==0 then print -1 else print A, B.
For more clarification refer to my solution
SOLUTIONS:
Editorialist's Solution
import java.util.Scanner;
import java.io.*;
class NXS2 {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int test = sc.nextInt();
while(test-->0){
int n = sc.nextInt();
int a=0,b=0;
for(int i=1;i<=n;i++){
int temp = n^i;
if(i<=temp && temp<=n){
a=i;
b=temp;
break;
}
}
if(a!=0 && b!=0)
System.out.println(a+" "+b);
else
System.out.println(-1);
}
}
}
Feel free to share your approach, if you want to. (even if it’s same) . Suggestions are welcomed as always had been.