Header Ads Widget

Equal by XORing | codechef solution

Rajnish Tripathi 21:40

 Problem

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

  • Select an integer � such that 1≤�<� and set �:=�⊕�. (Here, ⊕ 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≤�≤1000
  • 0≤�,�<230
  • 1≤�≤230

Subtasks

  • 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⊕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⊕1=25. Then we can perform the operation with �=2 which is <3. Therefore �=25⊕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() {
    // your code goes here
    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 {
// your code goes here
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--;
}
}
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments