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:
Input: N = 26
Output: 10 16
Explanation:
The Bitwise XOR of 10 and 16 is 26 and the difference between them is minimum.Input: N = 1
Output: 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(N2)
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 minimumvoid 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 Codeint main(){ int N = 26; findAandB(N); return 0;} |
Java
// Java program for the above approachpublic class MyClass{ // Function to find the numbers A and// B whose Bitwise XOR is N and the// difference between them is minimumstatic 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 approachfrom math import log2# Function to find the numbers A and# B whose Bitwise XOR is N and the# difference between them is minimumdef 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 Codeif __name__ == '__main__': N = 26 findAandB(N)# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;class GFG{// Function to find the numbers A and// B whose Bitwise XOR is N and the// difference between them is minimumstatic 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 Codepublic 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> |
10 16
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
