Data Modelling & AI Data Structure & Algorithm

Count ways to generate pairs having Bitwise XOR and Bitwise AND equal to X and Y respectively

23 June 2025

0

Given two integers X and Y, the task is to find the total number of ways to generate a pair of integers A and B such that Bitwise XOR and Bitwise AND between A and B is X and Y respectively

Examples:

Input: X = 2, Y = 5
Output: 2
Explanation:
The two possible pairs are (5, 7) and (7, 5).
Pair 1: (5, 7)
Bitwise AND = 5 & 7 = 2
Bitwise XOR = 5 ^ 7 = 5
Pair 2: (7, 5)
Bitwise AND = 7 & 5 = 2
Bitwise XOR = 7 ^ 5 = 5

Input: X = 7, Y = 5
Output: 0

Naive Approach: The simplest approach to solve the problem is to choose the maximum among X and Y and set all its bits and then check all possible pairs from 0 to that maximum number, say M. If for any pair of A and B, A & B and A?B becomes equal to X and Y respectively, then increment the count. Print the final value of count after checking for all possible pairs.
Time Complexity: O(M²), where M = max(X,Y)
Auxiliary Space: O(1)

Efficient Approach: The idea is to generate all possible combinations of bits at each position. There are 4 possibilities for the i^th bit in X and Y which are as follows:

If X_i = 0 and Y_i = 1, then A_i = 1 and B_i = 1.
If X_i = 1 and Y_i = 1, then no possible bit assignment exist.
If X_i = 0 and Y_i = 0 then A_i = 0 and B_i = 0.
If X_i = 1 and Y_i = 0 then A_i = 0 and B_i = 1 or A_i = 1 and B_i = 0, where A_i, B_i, X_i, and Y_i represent i^th bit in each of them.

Follow the steps below to solve the problem:

Initialize the counter as 1.
For the i^th bit, if X_i and Y_i are equal to 1, then print 0.
If at i^th bit, X_i is 1 and Y_i is 0 then multiply the counter by 2 as there are 2 options.
After that, divide X and Y each time by 2.
Repeat the above steps for every i^th bit until both of them become 0 and print the value of the counter.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to return the count of
// possible pairs of A and B whose
// Bitwise XOR is X and Y respectively
int countOfPairs(int x, int y)
{
    // Stores the count of pairs
    int counter = 1;
 
    // Iterate till any bit are set
    while (x || y) {
 
        // Extract i-th bit
        // of X and Y
        int bit1 = x % 2;
        int bit2 = y % 2;
 
        // Divide X and Y by 2
        x >>= 1;
        y >>= 1;
 
        // If Xi = 1 and Yi = 2,
        // multiply counter by 2
        if (bit1 == 1 and bit2 == 0) {
 
            // Increase required count
            counter *= 2;
            continue;
        }
 
        // If Xi =1 and Yi = 1
        if (bit1 & bit2) {
 
            // No answer exists
            counter = 0;
            break;
        }
    }
 
    // Return the final count
    return counter;
}
 
// Driver Code
int main()
{
    // Given X and Y
    int X = 2, Y = 5;
 
    // Function Call
    cout << countOfPairs(X, Y);
 
    return 0;
}

Java

// Java program for 
// the above approach
import java.util.*;
class GFG{
 
// Function to return the count of
// possible pairs of A and B whose
// Bitwise XOR is X and Y respectively
static int countOfPairs(int x, int y)
{
  // Stores the count of pairs
  int counter = 1;
 
  // Iterate till any bit are set
  while (x > 0 || y > 0) 
  {
    // Extract i-th bit
    // of X and Y
    int bit1 = x % 2;
    int bit2 = y % 2;
 
    // Divide X and Y by 2
    x >>= 1;
    y >>= 1;
 
    // If Xi = 1 and Yi = 2,
    // multiply counter by 2
    if (bit1 == 1 && bit2 == 0) 
    {
      // Increase required count
      counter *= 2;
      continue;
    }
 
    // If Xi =1 and Yi = 1
    if ((bit1 & bit2) > 0) 
    {
      // No answer exists
      counter = 0;
      break;
    }
  }
 
  // Return the final count
  return counter;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given X and Y
  int X = 2, Y = 5;
 
  // Function Call
  System.out.print(countOfPairs(X, Y));
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program for the above approach 
 
# Function to return the count of
# possible pairs of A and B whose
# Bitwise XOR is X and Y respectively
def countOfPairs(x, y):
 
    # Stores the count of pairs
    counter = 1
 
    # Iterate till any bit are set
    while(x or y):
 
        # Extract i-th bit
        # of X and Y
        bit1 = x % 2
        bit2 = y % 2
 
        # Divide X and Y by 2
        x >>= 1
        y >>= 1
 
        # If Xi = 1 and Yi = 2,
        # multiply counter by 2
        if (bit1 == 1 and bit2 == 0):
             
            # Increase required count
            counter *= 2
            continue
 
        # If Xi =1 and Yi = 1
        if(bit1 & bit2):
 
            # No answer exists
            counter = 0
            break
 
    # Return the final count
    return counter
 
# Driver Code
 
# Given X and Y 
X = 2
Y = 5
 
# Function call
print(countOfPairs(X, Y))
 
# This code is contributed by Shivam Singh

C#

// C# program for 
// the above approach
using System;
class GFG{
 
// Function to return the count of
// possible pairs of A and B whose
// Bitwise XOR is X and Y respectively
static int countOfPairs(int x, int y)
{
  // Stores the count of pairs
  int counter = 1;
 
  // Iterate till any bit are set
  while (x > 0 || y > 0) 
  {
    // Extract i-th bit
    // of X and Y
    int bit1 = x % 2;
    int bit2 = y % 2;
 
    // Divide X and Y by 2
    x >>= 1;
    y >>= 1;
 
    // If Xi = 1 and Yi = 2,
    // multiply counter by 2
    if (bit1 == 1 && bit2 == 0) 
    {
      // Increase required count
      counter *= 2;
      continue;
    }
 
    // If Xi =1 and Yi = 1
    if ((bit1 & bit2) > 0) 
    {
      // No answer exists
      counter = 0;
      break;
    }
  }
 
  // Return the readonly count
  return counter;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given X and Y
  int X = 2, Y = 5;
 
  // Function Call
  Console.Write(countOfPairs(X, Y));
}
}
  
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for
// the above approach
 
// Function to return the count of
// possible pairs of A and B whose
// Bitwise XOR is X and Y respectively
function countOfPairs(x, y)
{
  // Stores the count of pairs
  let counter = 1;
  
  // Iterate till any bit are set
  while (x > 0 || y > 0)
  {
    // Extract i-th bit
    // of X and Y
    let bit1 = x % 2;
    let bit2 = y % 2;
  
    // Divide X and Y by 2
    x >>= 1;
    y >>= 1;
  
    // If Xi = 1 and Yi = 2,
    // multiply counter by 2
    if (bit1 == 1 && bit2 == 0)
    {
      // Increase required count
      counter *= 2;
      continue;
    }
  
    // If Xi =1 and Yi = 1
    if ((bit1 & bit2) > 0)
    {
      // No answer exists
      counter = 0;
      break;
    }
  }
  
  // Return the final count
  return counter;
}
 
// Driver code
 
   // Given X and Y
  let X = 2, Y = 5;
  
  // Function Call
  document.write(countOfPairs(X, Y));
                             
</script>

Output:

Time Complexity: O(log M), where M = max(X,Y), as we are using a loop to traverse and each time we are decrementing by floor division of 2.
Auxiliary Space: O(1), as we are not using any extra space.

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!

Count ways to generate pairs having Bitwise XOR and Bitwise AND equal to X and Y respectively

C++

Java

Python3

C#

Javascript

Adding Persistent Memory to Claude Code with the Lightweight memsearch Plugin

GLM-5 vs. MiniMax M2.5 vs. Gemini 3 Deep Think: Which Model Fits Your AI Agent Stack?

We Extracted OpenClaw’s Memory System and Open-Sourced It (memsearch)

LEAVE A REPLY Cancel reply

Most Popular

The wait is over: Google just released Snapseed 4.0 for Android with a new pro camera

What to watch this weekend: Sally Field bonds with a talking octopus and British civil servants become ‘Legends’

Samsung Galaxy Buds 3 Pro receive stability update

Google might finally fix a Pixel problem that users have complained about for a decade

EDITOR PICKS

The wait is over: Google just released Snapseed 4.0 for Android with a new pro camera

What to watch this weekend: Sally Field bonds with a talking octopus and British civil servants become ‘Legends’

Samsung Galaxy Buds 3 Pro receive stability update

POPULAR POSTS

The wait is over: Google just released Snapseed 4.0 for Android with a new pro camera

What to watch this weekend: Sally Field bonds with a talking octopus and British civil servants become ‘Legends’

Samsung Galaxy Buds 3 Pro receive stability update

POPULAR CATEGORY

ABOUT US

FOLLOW US