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++
|
|
Time Complexity: O(1)
Auxiliary Space: O(1)
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.
