# Smallest pair of integers with minimum difference whose Bitwise XOR is N

Given a positive integer **N**, the task is to find the two smallest integers **A** and **B** such that the Bitwise XOR of **A** and **B** is **N** and the difference between **A** and **B** is minimum.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:N = 26Output:10 16Explanation:

The Bitwise XOR of 10 and 16 is 26 and the difference between them is minimum.

Input:N = 1Output:0 1

**Naive Approach:** The simplest approach to solve the given problem is to generate all possible pairs of the numbers over the range **[0, N]** and print that pair of numbers whose Bitwise XOR is the given number **N** and both the numbers are smallest.

**Time Complexity:** O(N^{2})**Auxiliary Space:** O(1)

**Efficient Approach:** The above approach can also be optimized based on the following observations:

- Consider the binary representation of any number is
**“1100011”**, then the number can be split around their Most Significant Bit(MSB) as**“1000000”**and**“100011”**and the Bitwise XOR of these numbers is the given number. - From the above splitting, it can be observed that the number formed by
**“1000000”**(say**A**) and**“100011”**(say**B**) is minimum and their difference between them is minimum as the value formed by**B**with always be smaller and closest to**A**.

From the above observations, the minimum value of **A** and **B** satisfying the given criteria is to split the given number **N** around its **Most Significant Bit(MSB)**.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the numbers A and` `// B whose Bitwise XOR is N and the` `// difference between them is minimum` `void` `findAandB(` `int` `N)` `{` ` ` `// Find the MSB of the N` ` ` `int` `K = log2(N);` ` ` `// Find the value of B` ` ` `int` `B = (1 << K);` ` ` `// Find the value of A` ` ` `int` `A = B ^ N;` ` ` `// Print the result` ` ` `cout << A << ` `' '` `<< B;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 26;` ` ` `findAandB(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `public` `class` `MyClass` `{` ` ` `// Function to find the numbers A and` `// B whose Bitwise XOR is N and the` `// difference between them is minimum` `static` `void` `findAandB(` `int` `N)` `{` ` ` `// Find the MSB of the N` ` ` `int` `K = (` `int` `)(Math.log(N) / Math.log(` `2` `));` ` ` `// Find the value of B` ` ` `int` `B = (` `1` `<< K);` ` ` `// Find the value of A` ` ` `int` `A = B ^ N;` ` ` `// Print the result` ` ` `System.out.println(A + ` `" "` `+ B);` `}` ` ` `public` `static` `void` `main(String args[]) {` ` ` `int` `N = ` `26` `;` ` ` `findAandB(N);` ` ` `}` `}` `// This code is contributed by SoumikMondal` |

## Python3

`# Python3 program for the above approach` `from` `math ` `import` `log2` `# Function to find the numbers A and` `# B whose Bitwise XOR is N and the` `# difference between them is minimum` `def` `findAandB(N):` ` ` ` ` `# Find the MSB of the N` ` ` `K ` `=` `int` `(log2(N))` ` ` `# Find the value of B` ` ` `B ` `=` `(` `1` `<< K)` ` ` `# Find the value of A` ` ` `A ` `=` `B ^ N` ` ` `# Print the result` ` ` `print` `(A, B)` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `N ` `=` `26` ` ` ` ` `findAandB(N)` `# This code is contributed by SURENDRA_GANGWAR` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` `// Function to find the numbers A and` `// B whose Bitwise XOR is N and the` `// difference between them is minimum` `static` `void` `findAandB(` `int` `N)` `{` ` ` ` ` `// Find the MSB of the N` ` ` `int` `K = (` `int` `)(Math.Log(N) /` ` ` `Math.Log(2));` ` ` `// Find the value of B` ` ` `int` `B = (1 << K);` ` ` `// Find the value of A` ` ` `int` `A = B ^ N;` ` ` `// Print the result` ` ` `Console.Write(A + ` `" "` `+ B);` `}` `// Driver Code` `public` `static` `void` `Main(String[] args)` `{` ` ` `int` `N = 26;` ` ` ` ` `findAandB(N);` `}` `}` `// This code is contributed by sanjoy_62` |

## Javascript

`<script>` ` ` `// JavaScript program for the above approach` ` ` `// Function to find the numbers A and` ` ` `// B whose Bitwise XOR is N and the` ` ` `// difference between them is minimum` ` ` `function` `findAandB(N) {` ` ` `// Find the MSB of the N` ` ` `let K = Math.log2(N);` ` ` `// Find the value of B` ` ` `let B = (1 << K);` ` ` `// Find the value of A` ` ` `let A = B ^ N;` ` ` `// Print the result` ` ` `document.write(A + ` `' '` `+ B);` ` ` `}` ` ` `// Driver Code` ` ` `let N = 26;` ` ` `findAandB(N);` ` ` `// This code is contributed by Potta Lokesh` ` ` ` ` `</script>` |

**Output:**

10 16

**Time Complexity:** O(1)**Auxiliary Space:** O(1)