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 :)
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'
#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; }
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?
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