 Flipping Bits EDITORIAL

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.