Find all possible pairs with given Bitwise OR and Bitwise XOR values

0 0 6 minutes read

Given two positive integers A and B representing Bitwise XOR and Bitwise OR of two positive integers, the task is to find all possible pairs (x, y) such that x ^ y is equal to A and x | y is equal to B.

Examples:

Input: A = 5, B = 7
Output:
2 7
3 6
6 3
7 2
Explanation:
7( XOR )2 = 5 and 7( OR )2 = 7
3( XOR )6 = 5 and 3( OR )6 = 7

Input: A = 8, B = 10
Output:
2 10
10 2

Brute Force Approach:

The brute force approach to solve this problem is to generate all possible pairs of positive integers and check if their bitwise XOR is equal to A and bitwise OR is equal to B. This can be done using two nested loops where the outer loop iterates through all positive integers up to B and the inner loop iterates through all positive integers up to the current index of the outer loop.

Here are the steps of approach:

Iterate through all positive integers up to B using a for loop.
For each integer i, iterate through all positive integers up to i using another for loop.
Check if the bitwise XOR of i and j is equal to A and the bitwise OR of i and j is equal to B.
If the condition is true, print the pair (j, i).
Continue with the outer loop until all positive integers up to B have been processed.
The output will be all the pairs of positive integers (x, y) such that x^y is equal to A and x|y is equal to B.

Below is the implementation of the above approach:

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find pairs with
// XOR equal to A and OR equal to B
void findPairs(int A, int B)
{
    for(int i=1; i<=B; i++){
        for(int j=1; j<=i; j++){
            if((i^j)==A && (i|j)==B){
                cout<<j<<" "<<i<<endl;
                if(i!=j)
                    cout<<i<<" "<<j<<endl;
            }
        }
    }
}
 
 
 
// Driver Code
int main()
{
    int A = 8, B = 10;
 
    findPairs(A, B);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    // Function to find pairs with
    // XOR equal to A and OR equal to B
    static void findPairs(int A, int B)
    {
        for (int i = 1; i <= B; i++) {
            for (int j = 1; j <= i; j++) {
                if ((i ^ j) == A && (i | j) == B) {
                    System.out.println(j + " " + i + "\n");
                    if (i != j)
                        System.out.println(i + " " + j
                                           + "\n");
                }
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int A = 8, B = 10;
 
        findPairs(A, B);
    }
}

Python3

# Python3 code for the above approach
 
# Function to find pairs with
# XOR equal to A and OR equal to B
def findPairs(A, B):
    for i in range(1, B+1):
        for j in range(1, i+1):
            if (i ^ j) == A and (i | j) == B:
                print(j, i)
                if i != j:
                    print(i, j)
 
A = 8
B = 10
findPairs(A, B)

C#

// C# code for the above approach
using System;
 
public class GFG
{   
    // Function to find pairs with
    // XOR equal to A and OR equal to B
    public static void FindPairs(int A, int B)
    {
        for (int i = 1; i <= B; i++)
        {
            for (int j = 1; j <= i; j++)
            {
                if ((i ^ j) == A && (i | j) == B)
                {
                    Console.WriteLine(j + " " + i);
                    if (i != j)
                        Console.WriteLine(i + " " + j);
                }
            }
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int A = 8, B = 10;
        FindPairs(A, B);
    }
}

Javascript

// Javascript code for the above approach
 
// Function to find pairs with
// XOR equal to A and OR equal to B
function findPairs(A, B) {
  for (let i = 1; i <= B; i++) {
    for (let j = 1; j <= i; j++) {
      if ((i ^ j) === A && (i | j) === B) {
        console.log(j + " " + i);
        if (i !== j) console.log(i + " " + j);
      }
    }
  }
}
 
// Driver Code
const A = 8, B = 10;
findPairs(A, B);

Output

2 10
10 2

Time Complexity: O(B^2), as we are using nested loops to iterate through all possible pairs of positive integers up to B.
Space Complexity: O(1), as we are not using any extra space.

Efficient Approach: The idea is to traverse through all possible values of x and use the property of XOR that if x ^ y = A, then x ^ A = y to find all possible values of y. Follow the steps below to solve the problem:

Iterate from 1 to B using a variable, say i, and perform the following operations:
- Initialize a variable y as i ^ A.
- Check if the value of y is greater than 0 and (i | y) is equal to B or not.
- If found to be true, then print the values of i and y.

Below is the implementation of the above approach:

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find pairs with
// XOR equal to A and OR equal to B
void findPairs(int A, int B)
{
    // Iterate from 1 to B
    for (int i = 1; i <= B; i++) {
        int y = A ^ i;
 
        // Check if (i OR y) is B
        if (y > 0 and (i | y) == B) {
            cout << i << " " << y << endl;
        }
    }
}
 
// Driver Code
int main()
{
    int A = 8, B = 10;
 
    findPairs(A, B);
    return 0;
}

Java

// Java code for the above approach
import java.util.*;
 
class GFG{
 
// Function to find pairs with
// XOR equal to A and OR equal to B
static void findPairs(int A, int B)
{
     
    // Iterate from 1 to B
    for(int i = 1; i <= B; i++) 
    {
        int y = A ^ i;
 
        // Check if (i OR y) is B
        if (y > 0 && (i | y) == B) 
        {
            System.out.println(i + " " + y);
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int A = 8, B = 10;
 
    findPairs(A, B);
}
}
 
// This code is contributed by Hritik

Python3

# Python3 code for the above approach
 
# Function to find pairs with
# XOR equal to A and OR equal to B
def findPairs(A, B):
     
    # Iterate from 1 to B
    for i in range(1, B + 1):
         
        y = A ^ i
         
        # Check if (i OR y) is B
        if (y > 0 and (i | y) == B):
            print(i, " ", y)
 
# Driver Code
A = 8
B = 10
 
findPairs(A, B)
 
# This code is contributed by amreshkumar3

C#

// C# code for the above approach
using System;
class GFG
{
     
    // Function to find pairs with
    // XOR equal to A and OR equal to B
    static void findPairs(int A, int B)
    {
          
        // Iterate from 1 to B
        for(int i = 1; i <= B; i++)
        {
            int y = A ^ i;
      
            // Check if (i OR y) is B
            if (y > 0 && (i | y) == B)
            {
                Console.WriteLine(i + " " + y);
            }
        }
    }
 
  // Driver code
  static void Main ()
  {
    int A = 8, B = 10;
  
    findPairs(A, B);
  }
}
 
// This code is contributed by suresh07.

Javascript

<script>
 
// JavaScript code for the above approach
 
 
// Function to find pairs with
// XOR equal to A and OR equal to B
function findPairs(A, B) {
    // Iterate from 1 to B
    for (let i = 1; i <= B; i++) {
        let y = A ^ i;
 
        // Check if (i OR y) is B
        if (y > 0 && (i | y) == B) {
            document.write(i + " " + y + "<br>");
        }
    }
}
 
// Driver Code
 
let A = 8, B = 10;
 
findPairs(A, B);
 
 
// This code is contributed by gfgking
 
</script>

Output

2 10
10 2

Time Complexity: O(B)
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 zambiatek!