1042 – Secret Origins

Problem Link

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

ll checkfor_same_count_ones(ll n)


ll co=0;




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


return co;

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

                                                                 [So how to Solve]

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

        Need better  Explanation? 


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() {
ll t,n,cs=1;

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

return 0;



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s