We know a way to count next number of same number of 1 bit

ll checkfor_same_count_ones(ll n)

{

ll co=0;

while(n)

{

co+=n&1;

n>>=1; // n/=2;

}

return co;

But the verdict will TLE ,because timelimit is .5 second;

[So how to Solve]

- First find the LSB [ let store on c= (n & -n) // if n=2 -n =-2
- add with the given number [r=c+n]
- Then Xor it with n
- Shift 2 bit right
- divide them with (n&-n) and
- last of all ,the result found from 3-5 step ,final result will be found by using this result | (c+n)

## View Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;ll num_of_same_1_count(ll n)

{

ll c=(n & -n);

ll r=n+c;

return ((r^n)>>2)/c|r;

}

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

ll t,n,cs=1;

cin>>t;

while(t–)

{

cin>>n;cout<<“Case “<<cs++<<“: “<<num_of_same_1_count(n)<<endl;

}

return 0;

}

Advertisements