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;

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]

  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() {
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

About waprogramming

I am in CSE,from CUET
This entry was posted in lightoj, Uncategorized and tagged . Bookmark the permalink.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s