PROBLEM LINK :
Medium to Tough
Given an integer N, you can perform the following operation at most once:
Choose an integer M and a “bitwise operator” and finally do the bitwise operation of M and N.
You need to output the minimum value of M such that the bitwise operation of M with N flips a maximum number of bits in the binary representation of N
If all bits of N is set (i.e N=2^n-1) where n is integer then Choose M =0 and do and(&) operation
Else choose M=2^(no of bit in n)-1; and do any operation which leads to give the most bit flipped
If all bits of N is set means when you do an AND operation with M=0 leads to all bit zero means Flipped all the bits with Minimum Possible M .
If all bits are not set means there is zero and one both in bit. So Two Conditions are Possible and in both conditions we will take M = 2(no of bit in N)-1;
- If no of Zero is more than No of one means our target is to flip zero bit with Minimum M we will do XOR operation between N and M
- If no of one is more than No of Zero means our target is to flip one bit with Minimum M we will do AND operation between N and M
TIME COMPLEXITY :
Only Time tacken to Find the No of Bit in N= O(LogN)
using namespace std;
#define fast_in_out ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
long long int n;
long long int tem =n;
long long int ans = pow(2,count)-1;
Feel Free to share and discuss your approach here.