# Counter game

# Counter game

+ 59 comments The problem can be solved in much simpler way. There's no requirement of several fancy functions, "power", "log" etc., just

*bit-manipulation*does the trick. Unfortunately, even "editorial" didn't give best/simplest of the solution. Let me share my approach for guys looking for better solution.

First of all, there's no need to "actually perform the operations on*N*". The game just requires counting*set-bits*in binary representation of*N-1*. This can be accomplished in**complexity, where***b=set-bits in (N-1)*. Here's code in C :int setBits(unsigned long long int n) { int count = 0 ; while(n) { n &= (n-1) ; count ++ ; } return count ; } int main() { int t ; scanf("%d\n",&t) ; while(t--) { unsigned long long int n ; scanf("%llu\n",&n) ; if (setBits(n-1) & 1) printf("Louise\n") ; else printf("Richard\n") ; } return 0; }

Obviously, language like Python gives even shorter solution. Hope this simplifies the problem to some extent.

Any comments/suggestions for further improvement are welcomed :)

+ 1 comment all you have to do is count the number of set bits, and the number of zeroes on the end less one.

def countergame(n): n = bin(n)[2:] n = n.split('1') turns = len(n)+len(n[-1])-2 return 'Louise' if turns&1 else 'Richard'

+ 2 comments #include<bits/stdc++.h> using namespace std; typedef unsigned long long ll; int main() { ll t; cin >> t; for(int i = 0;i<t;i++) { ll N,count = 0; cin >> N; N--; while(N!=0) { if(N%2)count++; N>>=1; } if(count%2)cout << "Louise" << endl; else cout << "Richard" << endl; } return 0; }

+ 4 comments there is some problem with the testcases i guess, because in the testcase#1. the 1st input is 6703734870638684097 and the 4th input is 6959712971461184279. both are not power of 2 and the lower power of 2 is 2^62, but if we see the output they have different answers. The first one has Richard, but the 3rd one has Louise. Can anyone please explain this?

+ 2 comments Hi Guys, I just submitted a code and it has been running for 10 mins. Can someone please kill the job?

-Thanks, Eshan

Sort 341 Discussions, By:

Please Login in order to post a comment