PROBLEM LINK :
Author : maazbinasad3
Tester : maazbinasad3
Editorialist : alkama_123
DIFFICULTY :
Medium to Tough
PREREQUISITES :
Bit Manupulation
PROBLEM :
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
QUICK EXPLANATION
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
EXPLANATION :
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)
SOLUTIONS :
Editorialist’s Solution
#include <bits/stdc++.h>
using namespace std;
#define fast_in_out ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main()
{
int t;
cin>>t;
while(t–)
{
long long int n;
cin>>n;
long long int tem =n;
int count=0;
while(n)
{
n=n/2;
count++;
}
long long int ans = pow(2,count)-1;
if(tem==ans)
cout<<0<<endl;
else
cout<<ans<<endl;
}
return 0;
}
Feel Free to share and discuss your approach here.