Boolean Evaluation DSA Problem Solution

Boolean Evaluation Queries DSA Problem Solution

In this post, we are going to solve Boolean Evaluation DSA Problem from Oracle, Online Assessments conducted on 13th October,2022. Let’s have a look at the problem statement first and then try to solve the problem.

Boolean Evaluation DSA Problem Statement

You are given 3 integers

A,

B, and

C. You have an expression as

((A|X)&(B|X)) = C. 

Determine if a number X exists such that the expression holds and if it does then print the minimum value of X else print -1.

Input

The first line contains

T, the number of test cases. For each test case the next 3 lines contains one parameter each namely A,B and C respectively where

(0A,B,C109).

Output

Output the minimum value of

X if

X exists else return -1.

Example
Input
2
8
11
9
3
2
1
Output
1
-1
Note

The & (bitwise AND) in C or C++ takes two numbers as operands and does AND on every bit of two numbers. The result of AND is 1 only if both bits are 1.

The | (bitwise OR) in C or C++ takes two numbers as operands and does OR on every bit of two numbers. The result of OR is 1 if any of the two bits is 1.

Problem Solution in 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 st = 0,en = INT_MAX;
while(st<=en){
int mid = st+(en-st)/2;
int val = (a|mid)&(b|mid);
// cout<<mid<<" "<<val<<endl;
if(val<c){
st = mid+1;
}else{
en = mid-1;
}
}
int val = (a|st)&(b|st);
if(val==c){
cout<<st<<endl;
}else{
cout<<-1<<endl;
}
}
return 0;
}

Problem Solution in Java

import java.util.*;
public class Main {
public static void main(String[] args) {

Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
boolean flag=false;
int ans=0;
int a=sc.nextInt();
int b=sc.nextInt();
int c=sc.nextInt();
for(int i=0;i<32;i++){
int ba=((a>>i)&1);
int bb=((b>>i)&1);
int bc=((c>>i)&1);
if(bc==0 && ba==1 && bb==1){
System.out.println(-1);
flag=true;
break;
}
else if(bc==1 && (bb==0 || ba==0)){
ans|=(1<<i);
}
}
if(!flag){
System.out.println(ans);
}
}

}
}