Given two integers A and B, the task is to check if there exists two integers P and Q over the range [1, A] and [1, B] respectively such that Bitwise XOR of P and Q is greater than A and B. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: X = 2, Y = 2
Output: Yes
Explanation:
By choosing the value of P and Q as 1 and 2 respectively, gives the Bitwise XOR of P and Q as 1^2 = 3 which is greater than Bitwise XOR of A and B A ^ B = 0.
Therefore, print Yes.Input: X = 2, Y = 4
Output: No
Naive Approach: The simplest approach to solve the given problem is to generate all possible pairs of (P, Q) by traversing all integers from 1 to X and 1 to Y and check if there exists a pair such that their Bitwise XOR is greater than Bitwise XOR of X and Y, then print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if there exists any pair (P, Q) whose// Bitwise XOR is greater than the Bitwise XOR of X and Yvoid findWinner(int X, int Y){ // Stores the Bitwise XOR of X & Y int playerA = (X ^ Y); bool flag = false; // Traverse all possible pairs for (int i = 1; i <= X; i++) { for (int j = 1; j <= Y; j++) { int val = (i ^ j); // If a pair exists if (val > playerA) { flag = true; break; } } if (flag) break; } // If a pair is found if (flag) cout << "Yes"; else cout << "No";}// Driver Codeint main(){ int A = 2, B = 4; findWinner(A, B); return 0;} |
C
// C program for the above approach#include <stdio.h>#include <stdbool.h>// Function to check if there exists any pair (P, Q) whose// Bitwise XOR is greater than the Bitwise XOR of X and Yvoid findWinner(int X, int Y){ // Stores the Bitwise XOR of X & Y int playerA = (X ^ Y); bool flag = false; // Traverse all possible pairs for (int i = 1; i <= X; i++) { for (int j = 1; j <= Y; j++) { int val = (i ^ j); // If a pair exists if (val > playerA) { flag = true; break; } } if (flag) break; } // If a pair is found if (flag) printf("Yes"); else printf("No");}// Driver Codeint main(){ int A = 2, B = 4; findWinner(A, B); return 0;}// This code is contributed by Sania Kumari Gupta |
Java
// Java program for the above approachimport java.lang.*;import java.util.*;class GFG{ // Function to check if there exists// any pair (P, Q) whose Bitwise XOR// is greater than the Bitwise XOR// of X and Ystatic void findWinner(int X, int Y){ // Stores the Bitwise XOR of X & Y int playerA = (X ^ Y); boolean flag = false; // Traverse all possible pairs for(int i = 1; i <= X; i++) { for(int j = 1; j <= Y; j++) { int val = (i ^ j); // If a pair exists if (val > playerA) { flag = true; break; } } if (flag) { break; } } // If a pair is found if (flag) { System.out.println("Yes"); } else { System.out.println("No"); }}// Driver codepublic static void main(String[] args){ int A = 2, B = 4; findWinner(A, B);}}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach# Function to check if there exists# any pair (P, Q) whose Bitwise XOR# is greater than the Bitwise XOR# of X and Ydef findWinner(X, Y): # Stores the Bitwise XOR of X & Y playerA = (X ^ Y) flag = False # Traverse all possible pairs for i in range(1, X + 1, 1): for j in range(1, Y + 1, 1): val = (i ^ j) # If a pair exists if (val > playerA): flag = True break if (flag): break # If a pair is found if (flag): print("Yes") else: print("No")# Driver Codeif __name__ == '__main__': A = 2 B = 4 findWinner(A, B)# This code is contributed by bgangwar59 |
C#
// C# program for the above approachusing System.Collections.Generic; using System; class GFG{ // Function to check if there exists// any pair (P, Q) whose Bitwise XOR// is greater than the Bitwise XOR// of X and Ystatic void findWinner(int X, int Y){ // Stores the Bitwise XOR of X & Y int playerA = (X ^ Y); bool flag = false; // Traverse all possible pairs for(int i = 1; i <= X; i++) { for(int j = 1; j <= Y; j++) { int val = (i ^ j); // If a pair exists if (val > playerA) { flag = true; break; } } if (flag) { break; } } // If a pair is found if (flag) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); }}// Driver codepublic static void Main(String[] args){ int A = 2, B = 4; findWinner(A, B);}}// This code is contributed by amreshkumar3 |
Javascript
<script>// JavaScript program for the above approach// Function to check if there exists// any pair (P, Q) whose Bitwise XOR// is greater than the Bitwise XOR// of X and Yfunction findWinner(X,Y){ // Stores the Bitwise XOR of X & Y let playerA = (X ^ Y); let flag = false; // Traverse all possible pairs for(let i = 1; i <= X; i++) { for(let j = 1; j <= Y; j++) { let val = (i ^ j); // If a pair exists if (val > playerA) { flag = true; break; } } if (flag) { break; } } // If a pair is found if (flag) { document.write("Yes<br>"); } else { document.write("No<br>"); }}// Driver codelet A = 2, B = 4;findWinner(A, B);// This code is contributed by unknown2108</script> |
Output:
No
Time Complexity: O(X * Y)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized based on the following observations:
- For any two integers P and Q, the maximum Bitwise XOR value is (P + Q) which can only be found when there are no common bits between P and Q in their binary representation.
- There are two cases:
- Case 1: If player A has two integers that produce the maximum Bitwise XOR value, then print “No”.
- Case 2: In this case, there must have some common bit between A and B such that there always exist two integers P and Q whose Bitwise XOR is always greater than the Bitwise XOR of A and B, where (P ^ Q) = (X | Y).
Therefore, from the above observations, the idea is to check if the value of given A^B is equal to A + B or not. If found to be true, then print “No”. Otherwise, print “Yes”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if there exists// any pair (P, Q) whose Bitwise XOR// is greater than the Bitwise XOR// of X and Yvoid findWinner(int X, int Y){ int first = (X ^ Y); int second = (X + Y); // Check for the invalid condition if (first == second) { cout << "No"; } // Otherwise, else { cout << "Yes"; }}// Driver Codeint main(){ int A = 2, B = 4; findWinner(A, B); return 0;} |
Java
// Java program for the above approachimport java.lang.*;import java.util.*;class GFG{ // Function to check if there exists// any pair (P, Q) whose Bitwise XOR// is greater than the Bitwise XOR// of X and Ystatic void findWinner(int X, int Y){ int first = (X ^ Y); int second = (X + Y); // Check for the invalid condition if (first == second) { System.out.println("No"); } // Otherwise, else { System.out.println("Yes"); }}// Driver codepublic static void main(String[] args){ int A = 2, B = 4; findWinner(A, B);}}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach# Function to check if there exists# any pair (P, Q) whose Bitwise XOR# is greater than the Bitwise XOR# of X and Ydef findWinner(X, Y): first = (X ^ Y) second = (X + Y) # Check for the invalid condition if (first == second): print ("No") # Otherwise, else: print ("Yes")# Driver Codeif __name__ == '__main__': A, B = 2, 4 findWinner(A, B)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to check if there exists// any pair (P, Q) whose Bitwise XOR// is greater than the Bitwise XOR// of X and Ystatic void findWinner(int X, int Y){ int first = (X ^ Y); int second = (X + Y); // Check for the invalid condition if (first == second) { Console.Write("No"); } // Otherwise, else { Console.Write("Yes"); }}// Driver codepublic static void Main(String[] args){ int A = 2, B = 4; findWinner(A, B);}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach// Function to check if there exists// any pair (P, Q) whose Bitwise XOR// is greater than the Bitwise XOR// of X and Yfunction findWinner(X,Y){ let first = (X ^ Y); let second = (X + Y); // Check for the invalid condition if (first == second) { document.write("No"); } // Otherwise, else { document.write("Yes"); }}// Driver Codelet A = 2, B = 4;findWinner(A, B);// This code is contributed by patel2127</script> |
Output:
No
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
