Given a natural number N our task is to find smallest number M having same length in binary representation as N such that difference between N | M (Bitwise-OR) and N ^ M (Bitwise-XOR) is maximum.
Examples :
Input : N = 5 Output : 5 Explanation : All number numbers having same length in binary representation as N are 4, 5, 6, 7. (5 | 4) - (5 ^ 4) = 4 (5 | 5) - (5 ^ 5) = 5 (5 | 6) - (5 ^ 6) = 4 (5 | 7) - (5 ^ 7) = 5 Hence smallest number having largest diference is M = 5 Input : N = 9 Output : 9
Naive Approach :
The idea is to find all the numbers having same length in binary representation as N and then for every number iterate (say i) and find smallest i having (N | i) – (N ^ i) maximum.
Efficient Approach :
Let M =0. Now, we can observe two cases
Case 1: When ith bit of N is set
In this case we will set the ith bit of M hence ith bit of N|M will be set and ith bit of N^M will be unset. So this will increase the difference between N|M and N^M. If we keep this bit of M unset, both N|M and N^M have this bit set and hence it will not increase the difference between them.
Case 2: When ith bit of N is unset.
In this case if we set this bit of M, both N|M and N^M will have this bit set or if we keep this bit of M unset both N|M and N^M will have this bit unset. So, in this case we cannot increase difference between them but as we have to output the minimum M possible so we will unset this bit of M.
From above observation it is clear that M = N.
Implementation :
//C++ implementation of above approach
#include<bits/stdc++.h>
using namespace std;
//Driver code
int main()
{
int N = 5;
cout<< "Required value of M is " << N;
return 0;
}
Time Complexity : O(1)
