Counter game
Counter game
AbhishekVermaIIT + 49 comments The problem can be solved in much simpler way. There's no requirement of several fancy functions, "power", "log" etc., just bitmanipulation 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 setbits in binary representation of N1. This can be accomplished in complexity, where b=setbits in (N1). Here's code in C :int setBits(unsigned long long int n) { int count = 0 ; while(n) { n &= (n1) ; count ++ ; } return count ; } int main() { int t ; scanf("%d\n",&t) ; while(t) { unsigned long long int n ; scanf("%llu\n",&n) ; if (setBits(n1) & 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 :)
rahulbhalley + 0 comments WOW man! You are a hacker.
ashuwp + 3 comments O(1) Solution for CPU's having builtin "popcnt" instruction.
int main() { int tc; cin >> tc; while (tc) { unsigned long long n; cin >> n; cout << (_popcnt64(n  1) & 1 ? "Louise" : "Richard") << endl; } return 0; }
AbhishekVermaIIT + 1 comment Thanks buddy !
That's a nice alternative to count setbits.
ashuwp + 2 comments O(1) Code for 64 bit Population Count
typedef unsigned long long ull; ull popcount(ull b) { b = (b >> 1) & 0x5555555555555555ULL; b = ((b >> 2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL); b = ((b >> 4) + b) & 0x0F0F0F0F0F0F0F0FULL; return (b * 0x0101010101010101ULL) >> 56; }
Ashish_Lalwaney + 0 comments Can you demonstrate a case where Louise wins?
jaybyrrd + 0 comments Thanks for posting this, but I have no idea how it works. Can you point me to a resource showing how? Or explain it.. Thanks.
Edit: I found that this is called a hamming weight: https://en.wikipedia.org/wiki/Hamming_weight
DrManhattan + 2 comments It's not an O(1) solution . As this >
_popcnt64(n1)
takes the same time as the previous suggested solution . The only difference is that it's faster to type this :)
shubhamitankr + 0 comments [deleted]ashuwp + 0 comments _popcnt(n) or _popcnt64(n) when compiled on a 64 bit CPU supporting SSE4.1 instructions, generate intrinsics which definitely run(s) in constant time.
However GCC compiler generates a lookup table implementation if mpopcnt is NOT passed as a parameter during compile. Although I guess it is fixed in latest versions.
Generic ASM implementation that uses intrinsics :static uint64_t POPCNT64(uint64_t x) { /* GNU GCC >= 4.2 supports the POPCNT instruction */ /* APD: Apple's gcc4.0 supports POPCNT and RHEL5's gcc4.1 supports POPCNT */ #if !defined(__GNUC__)  (__GNUC__ >= 4 && __GNUC_MINOR__ >= 1) __asm__ ("popcnt %1, %0" : "=r" (x) : "0" (x)); #endif return x; } #elif defined(__i386__)  defined(__i386) static uint32_t POPCNT32(uint32_t x) { /* GNU GCC >= 4.2 supports the POPCNT instruction */ #if !defined(__GNUC__)  (__GNUC__ >= 4 && __GNUC_MINOR__ >= 1) __asm__ ("popcnt %1, %0" : "=r" (x) : "0" (x)); #endif return x; }
manshujain2020 + 0 comments Nice Approach ....... but i haven't saw this function in any book .....
hexken + 1 comment Nice. Can you explain why the even/oddness of the popcount of n  1 gives us our answer?
AbhishekVermaIIT + 6 comments Sure. To understand this, lets look at everything in binary format.
First of all, for any number N to be power of two it must be of the format 100..00 (in binary) i.e. single 1 followed by all 0s. Now, consider the two operations allowed :
1) If N is not a power of 2, reduce the counter by the largest power of 2 less than N : This is equivalent to removing the first 1 until the number N is power of 2. Thus number of such operations would eqaute to count of all 1s before the last 1.Example : If N=11010, the largest power of 2 less than N would be 10000, reducing N by it we get 1010, which is equivalent to removing first 1.
2) If N is a power of 2, reduce the counter by half of N : This operation is equivalent to removing trailing zeros, or right shift. Number of such operations would be equal to count of all 0s after the final 1.
Combining the above two steps : we need to count "1s before last 1" and "0s after last 1". To bring uniformity in action, we subtract 1 from N, which will flip all the trailing zeros (and also last 1). Now, the only operation required, is to count 1s in the number i.e. to get popcount for (n1).hexken + 0 comments [deleted]hexken + 1 comment Thanks but I still can't see how you determine the winner without doing the operations. I think the last paragraph is the part I'm having trouble understanding. For example the popcounts of 6 and 5 are both 2, so how did popcount(6  1) tell you # of 1s before last 1 and # of 0s after last 1? (1 '1' before the first one and 61 '0's after the last '1'). I can't figure out how you determine the winner without doing the operations (right shifting by 1 or clearing left most bit).
This update (Update: If they set counter to 1, Richard wins, because its Louise' turn and she cannot make a move.) also doesn't make sense to me. If Louise can't make a move and n does not change then richard can't make a move either, and nobody ever makes a valid move, so by the rules of the game there should be no winner..?
Here is my submission so you can see that I understand how the operations look in binary, I just still dont get how popcount(n  1)&1 tells you the winner.
int main(void) { size_t t; scanf("%zu", &t); while (t) { uint64_t n; scanf("%lu", &n); uint64_t player = 0; while (n != 1) { uint64_t v; if ((v = n & (n  1))) { v = __builtin_clzl(n); n ^= 0x8000000000000000 >> v; } else { n >>= 1; } player ^= 1; } printf("%s\n", player == 0 ? "Richard" : "Louise"); } return 0; }
__builtin_clzl(n) gives the # of leading 0's before leftmost set bit
AbhishekVermaIIT + 20 comments Regarding the "update" : I feel the game is better defined in terms of loser. The person who fails to make a move loses, and hence, making the other one winner.
Let me take an example to demonstrate why popcount(n1)&1 works. It might seem trivial, yet, please bear with me ! Suppose N=1101001100(binary), then the operations will be : N is not power of 2  N = 1101001100 Louise will reduce it by 1000000000 N = 101001100 Richard will reduce it by 100000000 N = 1001100 Louise will reduce it by 1000000 N = 1100 Richard will reduce it by 1000  N(100) is power of 2  N = 100 Louise will reduce counter by half N = 10 Richard will reduce counter by half N = 1 Louise can't make a move, hence, loses Richard is the winner !
The above example shows that N=1101001100 can be better represented as "1101001
1
00", where we need to count "1s to the left of1
" and "0s to the right of1
", to know the total number of operations.Thus, total number of operations = 4 (1s in 1101001) + 2 (0s in
1
00) = 6. Since, this number (6) is even, hence, Richard wins.
This is all that is required to know the answer, but, as you can see, this forces us to do calculation in two parts : counting 1s and counting 0s.Somehow, if we could modify the "
1
00" part of "11010011
00" to "0
11" thus changing the number to "11010010
11", all we would need is to count 1s in this number i.e. setBits in the number.This final requirement to flip all trailing 0s to 1s and last
1
to0
(without modifying the other bits), can be easily achieved by subtracting 1 from the number N. For N=1101001100, we have N1 = 1101001011. Thus popcount(N1) gives the number of operations in the game, which gives winner depending upon if its even or odd.
Hope this clarifies the doubts, let me know if there's still any confusion.hexken + 1 comment Ahh now it makes perfect sense. Thanks a lot! Upon rereading your previous explanation I can't believe I didn't get it :/ This should be the editorial answer, it's a superior method and a better explanation.
AbhishekVermaIIT + 2 comments Awesome ! thanks a lot for the appreciation !
juhiduseja + 1 comment Your explanation was very lucid and helpful.Thanks!
Arun44 + 0 comments What a great explanation!! Was really insightful.Much better than the editorial.
nateshmbhat1 + 0 comments Thank you so much for this wonderful explaination ! :)
BlueSpirit + 1 comment I am trying your approach.
I am calculating numebr of 1s after subtracting by 1.unsigned long long int n; cin>>n; n = n1; int count =0; while(n!=0){ if((n&1) ==1) count++; n=n>>1; } (count&1==0)?cout
But its not working :(
AbhishekVermaIIT + 1 comment The posted "part of the code" looks fine to me. Please reexamine the completecode, in case, you have missed out something.
Do remember the first integer denotes the "number of testcases", and also make sure that you reset all variables before the execution of each testcase. These are the most common mistakes. If you still can't figure out the issue, please post your submission link, so that the entire code can be checked for error.
BlueSpirit + 0 comments Its working now. Thank you.
Last part(count&1 ==0)
was not working.
I was using it to check if count of1
s iseven
orodd
.
adityagupta6149 + 0 comments Never seen a better reply , thnx a lot.
nrby11 + 0 comments Mind Blown !!! Great Explanation :)
kantlove + 0 comments wow such a great explaination pal.
HaabyHings + 0 comments [deleted]huynhtastic + 0 comments 5 months after you posted this explanation, and it has completely enlightened me in digging deeper to find a more efficient way to do these algorithmic problems. Thank you for this detailed explanation.
devl1n + 0 comments How is this not mentioned in the editorial? Absolutely brilliant!! I did it in a similar way, but didn't subtract 1 from the number. Thanks for this solution!
GokayH + 0 comments Great explaantion and insight. Congratulations
Niharika_Volam + 0 comments Very clear explanation.Thanks a lot
jabongg + 0 comments Awsome explaination! really helped me.
15131A05K8_ + 0 comments amazing explination bro
Rishabhkv + 0 comments Thanks a lot sir @AbhishekVermaIIT
Atulkumar8 + 0 comments This is one of the best explanations to any question i have seen so far.
Atulkumar8 + 0 comments This is one of the best explanations to any question i have seen so far.
chaudhary__jr + 0 comments I read your comments and the things i got to learn or i got to revise from it were 1. If I want to flip bits of n I can subtract one from n. 2. If a number is a power of 2, it should be of the form 10000... Thanks a lot for sharing this brilliant solution.
rai_utkarsh + 0 comments Such a perfect explanation! Thank you so much!
wang_jinghui + 0 comments Awsome explaination!
shubhangiagarwa1 + 0 comments Brilliant explaination
ankushTripathi + 0 comments dude .. this is brilliant..
hackShashi + 0 comments Insane dude! Keep it up.
J_sai_krishna + 0 comments very nice explanation thank you :)
ayushjainsir + 0 comments nicely explained sir, first time saw u on the discussion of reverse shuffle merge from that time i became ur fan
smnradeon + 0 comments taaliya !!!
shikharkunal99 + 2 comments for t in range(input()):
on = sum(b=='1' for b in bin(input()1)[2:]) if on&1: print "Louise" else: print "Richard"
AbhishekVermaIIT + 1 comment Very concise O(n) solution in python. Cool !
Edit : Here n is the length of input N in binary form.
shikharkunal99 + 1 comment It's O(log n). Conversion to binary can be done in log n steps and then then length of the binary number is also log n.
AbhishekVermaIIT + 0 comments Actually, I considered n as the length of input in binary form, same as assumed in editorial (while mentioning timecomplexity). You are right considering n as input though. Sorry, for the confusion, I have added this to my previous response. Its a nice solution :)
ntadiko + 0 comments We are not supposed to give away answers here. But I would like to suggest you a correction. intstead of sum([..]) go with (bin(input()1)[2:]).count('1')
ank11 + 0 comments Nice Explanation
Kunal0508 + 0 comments Amazing technique and also explained very well!!
chandra130313 + 0 comments How can I include my own defined library in hackerrank.
vidushig2 + 0 comments but how
vidushig2 + 1 comment if we dont use unsignedit is giving wrong answer... why?
AbhishekVermaIIT + 0 comments That's because "long long int" uses 64 bits, hence, the range is from 2^63 to 2^631. Since, the range for N (mentioned in "Constraints") is 0 to 2^641, it can't be stored properly in "long long int" and hence gives wrong result.
Instead, using "unsigned long long int" (still using 64 bits), the range becomes 0 to 2^641, which is the required range for N.
I_love_Pournima + 1 comment Can you explain how you came up with the approach? Counting the set bits in N1 seems totally unrelated
AbhishekVermaIIT + 0 comments "The other post (above) explaining the logic" is exactly how I reached the logic. I usually prefer mathematical solutions because of better timecomplexity.
While trying to find a mathematical pattern, I concluded that I required the count of "initial 1s and final 0s". Further, instead of counting 1s and 0s, I wanted to reach a unified solution. Thinking over that I realized "bits in N1" would allow me do that, hence, the solution. For detailed explanation, please check the reply above.
tat_lim + 0 comments [deleted]tat_lim + 2 comments Java supports bitCount (a.k.a. Population Count or "popcnt") since JDK 1.5 (released in 2004), so the following is the simplest and fastest Java solution in O(1).
Java Solution in O(1)
long N = Long.parseUnsignedLong(in.next()); boolean LouiseWins = (Long.bitCount(N1)&1) != 0; System.out.println(LouiseWins? "Louise" : "Richard");
exceptionalasif + 0 comments Can you please explain the part
(Long.bitCount(N1)&1) != 0;
Thanks!sayamqazi + 1 comment This is not a O(1) solution. the bitCount function runs in O(log n) so the complexity is O(log n).
tat_lim + 2 comments Well, according to the Java implementation of "Long.bitCount", the complexity is indeed O(1). Please read the following URL for further evidence: http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/2d585507a41b/src/share/classes/java/lang/Long.java
sayamqazi + 1 comment Yes i know the bitcount function is O(1) within the problem constraints. If we study the problem with pure mathematical point of view you will see that bitCount function is a O(n) function where n is the number of bits in the data_type on which the bitCount funciton is called.
bitCount(long n) //it is O(1) bitCount( arbitrary_data_type) //it is O(N) where n is num_bits
tat_lim + 0 comments From our pure mathematical point of view, the complexity of Java "bitCount" method is O(K) because it takes exactly the same number of operations (namely, "K") to compute the "bitCount" for any value of N. Since K is a constant and independent of N, the complexity may be rewritten as O(K) = O(1). Therefore, the complexity of "bitCount" is indeed O(1). Please feel free to read the following URL for further evidence: http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/2d585507a41b/src/share/classes/java/lang/Long.java
randhawarahul069 + 1 comment Broken link. Here is the alternate working link: https://zgrepcode.com/java/openjdk/10.0.2/java.base/java/lang/long.java#L1825
tat_lim + 0 comments Well, actually your link "IS" broken. The following is a correct link since 2009:
http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/2d585507a41b/src/share/classes/java/lang/Long.java
anindya_tnt + 1 comment I would like to know how you came up with this solution. What was your approach stepwise in coming up with this technique? That would really be of help to me.
AbhishekVermaIIT + 0 comments Hi Aninda ! I have replied to similar question above, have a look if it answers your query.
The basic approach that can be followed is : Instead of tackling the problem "literally", try to get insight into the problem. It will lead to 'some' solution. Optimize the original solution, if possible, using mathematics and algorithms. Roughly, that's what I did for this problem.
akshaybaura + 4 comments int t; unsigned long long int n; cin>>t; for(int i=1;i<=t;i++) {int count=0; cin>>n; while(n!=1) { if(!(n & (n1))) n=n/2; else n=npow(2,floor(log (n)/log (2))); count++ ; } if(count%2==0) cout<<"Richard"<<endl; else cout<<"Louise"<<endl; }
can i plz get some help on this... test cases are rejecting this code..
charandattab + 0 comments Your code is right. You just need to write your own power function. POW function doesnot return Unsigned long long int value.
eclipsecode + 0 comments Cast the
pow
function to unsigned long long intFor ex:
(unsigned long long int) pow(unsigned long long int 2,unsigned long long int x);
anilkaliya_au + 0 comments why u used n=npow(2,floor(log (n)/log (2))); if n is not a poweer of two then reduce it to nearest small power of 2 less than n ryt? then why not n=pow(2,floor(log (n)/log (2))); e.g n=7; pow(2,floor(7)/floor(2))=4; now n shoud be 4 not 74 m i ryt?
anilkaliya_au + 0 comments sorry i got it!!!!
practice_match + 0 comments I just want to know the nearest number in 2^x to the given no will be played by louise, and then alternately.
So if x is even then Richard wins if x is odd Louise wins, what is wrong in this. Please help
dguai + 0 comments Thanks for this genius solution. I am absolutely blown away with this solution,
naveenbanda + 0 comments I have just seen magic!! Thanks for such a nice solution and explaination. It clears some basic concepts of bit magic!!
samikshya_chand1 + 2 comments why does long long give wrong answer,whereas unsigned long long passes all the test cases?
AbhishekVermaIIT + 0 comments I have already replied to this query above.
ankibansal56 + 0 comments That's because long long is used to store 2^63 to (2^63)1 because last bit is used as sign bit in long long where as in unsigned all bits are used for magnitude hence giving you a range of 0 to (2^64)1
God_Speed + 1 comment i am trying to solve the question by doing operations on n....but getting only 11 points....please help where am i going wrong
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int t; cin>>t; for(int v=1;v<=t;v++) { long long n,c=0; cin>>n; while(n>1) { if(((n)&(n1))==0) n=n(n/2); else n = n  pow(2,floor(log(n)/log(2))); //cout<<n<<" "; c++; } //cout<<c; if(c%2==0) cout<<"Richard"<<endl; else cout<<"Louise"<<endl; } return 0; }
AbhishekVermaIIT + 0 comments Declare n as
unsigned long long n
instead oflong long n
.You'll also need different pow() to handle unsigned long long values.
arkham_bat + 1 comment Hey Abhishek, can you please explain how you come up with that "counting setbits in binary representation of N1" concept....
AbhishekVermaIIT + 1 comment Hey Satish, I have replied to same query above. Please have a look at it.
arkham_bat + 1 comment Yeah...got to see that after posting the comment.....wonderful explanation....
One request....
Is there some online material to learn some very useful bit manipulation tricks.....would love to hear from you.
AbhishekVermaIIT + 0 comments Thanks for the appreciation! Currently, I am not aware of anything such. But, I am working towards creating something of that sort. If things go as planned, I'll update with one soon.
bazuka_ + 0 comments what's the problem with my code can you please explain me?
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int t,cnt; unsigned long long int n; cin>>t; for(int i=0;i<t;i++) { cnt=0; scanf("%llu",&n); if(n==1) {cout<<"Richard"<<endl;continue;} while(n>1) { if((n&1)==0) { n=n/2; } else { while (n & (n1)) { n = n & (n1); } n=n/2; } cnt++; } if(cnt%2==0) cout<<"Richard"<<endl; else cout<<"Louise"<<endl; } /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }
Lokesh9 + 1 comment check your solution for counter value 11 and 12 according to the question Louise should win the game in both the cases but according to your solution Richard and Louise respectively are winner please check it out
AbhishekVermaIIT + 0 comments That's not true, 11 and 12 won't have the same winner (according to question too) ! Here's the operation sequence for both values, please check where you differ in opinion :
11 12 Louise 3 4 Richard 1 (wins) 2 Louise 1 (wins)
seeni0424 + 0 comments Congrats. **#AbhishekVermaIIT **can you explain how that bit manipulation works.
intrunder + 0 comments can u explain ur setBits function i am not familiar with bit manipulation??
9weishi + 0 comments [deleted]wei_shi02 + 0 comments [deleted]peehu65me + 1 comment sir just one question u might be thinking that i am insane but n&=(n1); is assigning value true(1) or false(0) right? then how it is working i don't get it
AbhishekVermaIIT + 0 comments The statement
n &= (n1)
is short forn = n & (n1)
. This means we are applying "bitwise AND" betweenn
andn1
, and storing the result inn
.Every iteration of this statement reduces setbits in
n
by 1. So, eventually the value ofn
becomes 0 when there are no setbits left. The conditionwhile(n)
checks exactly for this, and continues to run whilen
is nonzero. Thus, the number of iterations of loop will be same as the number of setbits, which is stored in variablecount
and returned as result.If
while(n)
confuses you, replace it bywhile (n != 0)
. Both have the same effect.
chung2000 + 0 comments Your solution is truly brilliant. I have to admit that I needed to read your later explanation to fully get it and be able to try a Python solution. Thank you.
#!/bin/python3 import sys players = "Richard", "Louise" T = int(input().strip()) for i in range(T): N = int(input().strip()) # Based on awesome solution from AbhishekVermaIIT print(players[bin(N1).count("1")%2])
shrewga + 0 comments I counted the number of bits set in n and added the position of LSB. I know, it involved two loops because of that. Totally unnecessary I have realized. This is great though! Thanks for sharing!
sailorsiraj + 0 comments Its a very intelligent way to do this program. Your explanation below was very helpful. Thanks.
tomasz_gawel + 0 comments And how about this?
unsigned t; unsigned long n; const auto size = sizeof(n) * 8; cin >> t; while (t > 0) { cin >> n; unsigned long last, count = 0, mask = 1UL << (size  1); for (unsigned i = 0; i < size; i++, mask >>= 1) if ((mask & n) != 0) count++, last = i; auto isOdd = (count + (size  last)) % 2 == 1; cout << (isOdd ? "Louise" : "Richard") << endl; }
avijha + 0 comments WOW! Perfect use of Brian Kernighanâ€™s Algorithm. Hats off to you buddy...
metamemelord + 2 comments Can you please detect error in my approach?
q = int(input()) for i in range(q): n = int(input()) l = len(bin(n))  2 #length of bin num s = '' for i in range(l1): s += '1' k = int(s,2)+1 #Get power of 2 less than n if n!=k: #If n and k are n not equal, then it means Richard uses first step to make value to power of two. l += 1 #In a l length number, the game is performed by l+1 times now because n!=k. So increment l if l%2 == 0: #If l is even, Richard wins. print('Richard') else: #Else Louise wins. print('Louise')
AbhishekVermaIIT + 2 comments Gaurav, the logic needs to be modified. While N is not power of 2, both players reduce N by power of 2 (not to power of 2).
For example, if N=15, Louise will reduce N by 8 to get N=7, which is not power of 2.
Another issue is that number of turns is not related to binarylength of number. Please try to run few examples using the logic, you'll surely get it.
metamemelord + 0 comments [deleted]metamemelord + 1 comment I understood the logic and wrote a one liner to solve the problem. Here's the code:
print('Richard') if str(bin(int(input())1)).count('1')%2 == 0 else print('Louise')
Thanks a lot for explaining the logic nicely! :)
AbhishekVermaIIT + 1 comment Very well coded ! It makes problem look too easy for Python coders ! :)
purvee_agrawal + 1 comment print('Richard') if str(bin(int(input())1)).count('1')%2 == 0 else print('Louise')
Could you explain this logic?
eclipsecode + 0 comments bin(int(input())1) bin converts the input to binary representation then you are converting it to string and counting the no of 1's in that string
since Louise and Richard playing the game on alternate turn so if the no of 1's are even then Richard wins otherwise Louise wins
purvee_agrawal + 1 comment How is the line k = int(s,2)+1, giving the result 4? what's the meaning of (s,2) and then that is typecasted to int? Could you explain the meaning of(s,2)?
eclipsecode + 1 comment if you do int(S, B), it says convert S, which is the string representation of a number in base B
like int('10', 2) = 2
int('10', 3) = 3
purvee_agrawal + 1 comment Thank you!
eclipsecode + 0 comments Welcome
AbhishekDre + 0 comments The setBits function uses Brian Kernighanâ€™s algorithm to count the number of set bits.
prasanthfryo + 0 comments wonderful Solution Bro ...! ;)
ravva_phanesh + 0 comments Nice innovative solution :)
fdesu + 0 comments For those, who might wonder, here's java solution.
static String counterGame(long n) { return (Long.bitCount(n  1)  1 & 1) == 0 ? "Louise" : "Richard"; }
I did it almost independently, and the key, as probably was noticed, to look into equivalence of cases
n
andn  1
.pavitra_ag + 0 comments HOW ABOUT THIS?
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <bitset> using namespace std; int main() { long long int t,x,y,b; cin>>t; for(long long int i=0;i<t;i++) { long long int n; cin>>n; b=0; while(n!=1) { x=n&(n1); if(x==0) n=n/2; else { y=63; bitset <64> b1(n); while(b1[y]!=1) { y; } n=npow(2,y); } b=b^1; } if(b==0) cout<<"Richard\n"; else cout<<"Louise\n"; } return 0; }
rishavrrj1 + 0 comments Gawd level _/_
mohitsolanki8391 + 0 comments i can't understand if (setBits(n1) & 1)
can you explain with example ???sidajwalia + 0 comments mind blown explanation and thinking process. Thank you very much.
subhajit104 + 0 comments can you explain plz ?
akhilgautam123 + 0 comments For setBits function using Brian Kernighanâ€™s Algorithm took O(log n). So how this solution is only in O(b). I am a beginner in time complexities. An explaination would be greatly appreciated.
Ajay_EEE19 + 0 comments but why N1 ?
mayank7577 + 0 comments can you please explain the logic how you arrived to this approach, I am not able to visualise the scenario.
balajilitsv + 0 comments Can you explain the mathematical or pratical reason behind this solution? I'm little bit confused on how your solution gives the correct answer.
HELICpros + 0 comments Can someone please explain what is happening in the
if (setBits(n1) & 1)
part of the code???
Dick_Grayson + 0 comments That's great code right there
ashu23bhardwaj + 0 comments can you please explain why you subtracted n by 1?
shreyas_keote + 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?
yesudeep + 1 comment The test cases are alright, I think. Here's some Python code that works for your test cases too. It took me quite some time to crack this, but it was well worth it. Initially, I faced timeouts because I was subtracting the exponent instead of the largest power of 2 less than n.
Check this out:
def read_int(): return int(raw_input()) def is_power_of_2(n): return n & (n  1) == 0 def log2(n): assert n > 0 exp = 0 while n: n >>= 1 exp += 1 return exp def largest_exp_of_2_less_than(n): return log2(n)  1 def steps(n): i = 0 while n > 1: if is_power_of_2(n): n >>= 1 else: n = 1 << largest_exp_of_2_less_than(n) i += 1 return i  1 def is_even(n): return not (n & 1) def main(): t = read_int() assert 0 < t < 11 for i in range(t): print("Louise" if is_even(steps(read_int())) else "Richard") if __name__ == '__main__': main()
syed_moinudeen + 0 comments Hi yesudeep, thanks for the hints! I have a little doubt though. How does the no. of steps being even gives "Louise" as the answer? I'm not able to catch the logic :)
srikanth_poolla + 0 comments yes shreyas i too experienced the same prob .. coz if its an even exponent then richard wins and viceversa .. but the test cases contradict
mesutekici + 0 comments Hi shreyas, I agree with you,
After spending too much time on this, I finally quit and downloaded one of the test cases. for 12538990046817067955 (63 bit) the answer was Louise for 10705863057888060538 (63 bit) the answer was Richard 1<<63= 9223372036854775808
If I am not misunderstanding this problem, test case is wrong for > 63 bit
regards
herodragon1990 + 0 comments You are right Shreyas, testcases are not correct. I have figured out half of number of testcases are wrong. But, how I can get throught this in order to move to next challenge Shreyas?
k_i_d_h_a_r + 1 comment #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; }
apghr + 0 comments writing N was a clever trick, thumbs up.
eshantandon + 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
Sig11 + 0 comments Hi Admin, My Submissions are also running for past 20 hrs[Processing] !! Can u pls kill it ?
Thanks Vinish
dheerajChallenge Author + 1 comment Hi @ Sig11,
your submission has been processed. Please have a look.
competitivecoder + 0 comments @dheeraj can you take a look at my submission.I have unlocked the solution but still could not get what's wrong.My submission Id https://www.hackerrank.com/challenges/countergame/submissions/code/12392799
shraddha416 + 0 comments can anyone tell the error in this code??? i guess my logic is correct but m failing for almost half of the test cases
int main() {
int t; cin>>t; for(int i=0;i<t;i++) { unsigned long long int n; cin>>n; int count=0; while(n!=1) { float f=log2(n); if(f>(int)f) n=npow(2,int(f)); else n=n/2; count++; } if(count%2!=0) cout<<"Louise"<<endl; else cout<<"Richard"<<endl; } return 0;
}
mukul_dhariwal94 + 0 comments made a video about how we can think to solve this 
pruhujatra + 0 comments 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'
frobeniusfg + 0 comments C++:
#include <iostream> int main() { for (long int n, k = 0, a = (std::cin >> a, a); a; a, k = 0) { for (std::cin >> n, n; n; k += n & 1, n >>= 1); std::cout << (k & 1 ? "Louise" : "Richard") << std::endl; } return 0; }
ssshukla26 + 0 comments #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> unsigned int isPowerOfTwo(unsigned long long int n) { return (n && (!(n & (n1)))); } unsigned long long int largestPowerOfTwo(unsigned long long int n) { while(n & (n1)) { n = n & (n1); } return n; } void CG(unsigned long long int n) { if(n == 1) { printf("Richard\n"); } else { int lr = 0; while (n != 0) { if(isPowerOfTwo(n)) { //If N is a power of 2, reduce the counter by half of N n = n / 2; } else { //if N is not a power of 2, reduce the counter by the largest power of 2 less than N n = largestPowerOfTwo(n); } lr++; } if(lr%2) printf("Richard\n"); else printf("Louise\n"); } } int main() { int T; unsigned long long int N; scanf("%d", &T); for(int i = 0; i < T; i++) { scanf("%llu", &N); CG(N); } return 0; }
aditya_johri + 0 comments what's the problem in this for big integer answer is wrong almost 20 digits
for(i=1;i<=t;i++) { c=0; unsigned long n; cin>>n; while(n!=1) { c++; if(log2(n)int(log2(n))!=0) { n=npow(2,int(log2(n))); } else { n=n/2; } } if(c%2==0) { cout<<"Richard"<<endl; } else if(c==0) { cout<<"Richard"<<endl; } else { cout<<"Louise"<<endl; } }


Sort 231 Discussions, By:
Please Login in order to post a comment