AbhishekVermaIIT 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 :)
rahulbhalley WOW man! You are a hacker.
ashuwp 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 Thanks buddy !
That's a nice alternative to count set-bits.
ashuwp 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 Can you demonstrate a case where Louise wins?
jaybyrrd 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 It's not an O(1) solution . As this -->
_popcnt64(n-1)
takes the same time as the previous suggested solution . The only difference is that it's faster to type this :)
shubhamitankr [deleted]ashuwp _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 look-up 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 gcc-4.0 supports POPCNT and RHEL5's gcc-4.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; }
hexken Nice. Can you explain why the even/oddness of the popcount of n - 1 gives us our answer?
AbhishekVermaIIT 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 (n-1).hexken [deleted]hexken 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 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(n-1)&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
100", 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
100) = 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 "
100" part of "1101001100" to "011" thus changing the number to "1101001011", 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
1to0(without modifying the other bits), can be easily achieved by subtracting 1 from the number N. For N=1101001100, we have N-1 = 1101001011. Thus popcount(N-1) 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 Ahh now it makes perfect sense. Thanks a lot! Upon re-reading 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 Awesome ! thanks a lot for the appreciation !
juhiduseja Your explanation was very lucid and helpful.Thanks!
Arun44 What a great explanation!! Was really insightful.Much better than the editorial.
nateshmbhat1 Thank you so much for this wonderful explaination ! :)
BlueSpirit I am trying your approach.
I am calculating numebr of 1s after subtracting by 1.unsigned long long int n; cin>>n; n = n-1; int count =0; while(n!=0){ if((n&1) ==1) count++; n=n>>1; } (count&1==0)?coutBut its not working :(
AbhishekVermaIIT The posted "part of the code" looks fine to me. Please re-examine the complete-code, 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 test-case. 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 Its working now. Thank you.
Last part(count&1 ==0)was not working.
I was using it to check if count of1s isevenorodd.
adityagupta6149 Never seen a better reply , thnx a lot.
nrby11 Mind Blown !!! Great Explanation :)
kantlove wow such a great explaination pal.
HaabyHings [deleted]
huynhtastic 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 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 Great explaantion and insight. Congratulations
Niharika_Volam Very clear explanation.Thanks a lot
jabongg Awsome explaination! really helped me.
15131A05K8_ amazing explination bro
Rishabhkv Thanks a lot sir @AbhishekVermaIIT
Atulkumar8 This is one of the best explanations to any question i have seen so far.
Atulkumar8 This is one of the best explanations to any question i have seen so far.
chaudhary__jr 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 Such a perfect explanation! Thank you so much!
wang_jinghui Awsome explaination!
shubhangiagarwa1 Brilliant explaination
ankushTripathi dude .. this is brilliant..
hackShashi Insane dude! Keep it up.
J_sai_krishna very nice explanation thank you :)
ayushjainsir nicely explained sir, first time saw u on the discussion of reverse shuffle merge from that time i became ur fan
smnradeon taaliya !!!
shikharkunal99 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 Very concise O(n) solution in python. Cool !
Edit : Here n is the length of input N in binary form.
shikharkunal99 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 Actually, I considered n as the length of input in binary form, same as assumed in editorial (while mentioning time-complexity). 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 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 Nice Explanation
Kunal0508 Amazing technique and also explained very well!!
chandra130313 How can I include my own defined library in hackerrank.
vidushig2 but how
vidushig2 if we dont use unsignedit is giving wrong answer... why?
AbhishekVermaIIT That's because "long long int" uses 64 bits, hence, the range is from -2^63 to 2^63-1. Since, the range for N (mentioned in "Constraints") is 0 to 2^64-1, 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^64-1, which is the required range for N.
I_love_Pournima Can you explain how you came up with the approach? Counting the set bits in N-1 seems totally unrelated
AbhishekVermaIIT "The other post (above) explaining the logic" is exactly how I reached the logic. I usually prefer mathematical solutions because of better time-complexity.
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 N-1" would allow me do that, hence, the solution. For detailed explanation, please check the reply above.
tat_lim [deleted]tat_lim 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(N-1)&1) != 0; System.out.println(LouiseWins? "Louise" : "Richard");exceptionalasif Can you please explain the part
(Long.bitCount(N-1)&1) != 0;Thanks!sayamqazi This is not a O(1) solution. the bitCount function runs in O(log n) so the complexity is O(log n).
tat_lim 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 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 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 Broken link. Here is the alternate working link: https://zgrepcode.com/java/openjdk/10.0.2/java.base/java/lang/long.java#L-1825
tat_lim Thank you!
anindya_tnt 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 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 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 & (n-1))) n=n/2; else n=n-pow(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 Your code is right. You just need to write your own power function. POW function doesnot return Unsigned long long int value.
eclipsecode Cast the
powfunction to unsigned long long intFor ex:
(unsigned long long int) pow(unsigned long long int 2,unsigned long long int x);anilkaliya_au why u used n=n-pow(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 7-4 m i ryt?
anilkaliya_au sorry i got it!!!!
practice_match 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 Thanks for this genius solution. I am absolutely blown away with this solution,
naveenbanda I have just seen magic!! Thanks for such a nice solution and explaination. It clears some basic concepts of bit magic!!
samikshya_chand1 why does long long give wrong answer,whereas unsigned long long passes all the test cases?
AbhishekVermaIIT I have already replied to this query above.
ankibansal56 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 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)&(n-1))==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 Declare n as
unsigned long long ninstead oflong long n.You'll also need different pow() to handle unsigned long long values.
arkham_bat Hey Abhishek, can you please explain how you come up with that "counting set-bits in binary representation of N-1" concept....
AbhishekVermaIIT Hey Satish, I have replied to same query above. Please have a look at it.
arkham_bat 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 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_ 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 & (n-1)) { n = n & (n-1); } 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 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 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 Congrats. **#AbhishekVermaIIT **can you explain how that bit manipulation works.
intrunder can u explain ur setBits function i am not familiar with bit manipulation??
9weishi [deleted]wei_shi02 [deleted]peehu65me sir just one question u might be thinking that i am insane but n&=(n-1); is assigning value true(1) or false(0) right? then how it is working i don't get it
AbhishekVermaIIT The statement
n &= (n-1)is short forn = n & (n-1). This means we are applying "bitwise AND" betweennandn-1, and storing the result inn.Every iteration of this statement reduces set-bits in
nby 1. So, eventually the value ofnbecomes 0 when there are no set-bits left. The conditionwhile(n)checks exactly for this, and continues to run whilenis non-zero. Thus, the number of iterations of loop will be same as the number of set-bits, which is stored in variablecountand returned as result.If
while(n)confuses you, replace it bywhile (n != 0). Both have the same effect.
chung2000 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(N-1).count("1")%2])
shrewga 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 Its a very intelligent way to do this program. Your explanation below was very helpful. Thanks.
tomasz_gawel 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 WOW! Perfect use of Brian Kernighan’s Algorithm. Hats off to you buddy...
metamemelord 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(l-1): 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 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 binary-length of number. Please try to run few examples using the logic, you'll surely get it.
metamemelord [deleted]metamemelord 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 Very well coded ! It makes problem look too easy for Python coders ! :)
purvee_agrawal print('Richard') if str(bin(int(input())-1)).count('1')%2 == 0 else print('Louise')
Could you explain this logic?
eclipsecode 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 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 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 Thank you!
eclipsecode Welcome
AbhishekDre The setBits function uses Brian Kernighan’s algorithm to count the number of set bits.
prasanthfryo wonderful Solution Bro ...! ;-)
ravva_phanesh Nice innovative solution :)
fdesu 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
nandn - 1.pavitra_ag 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&(n-1); if(x==0) n=n/2; else { y=63; bitset <64> b1(n); while(b1[y]!=1) { y--; } n=n-pow(2,y); } b=b^1; } if(b==0) cout<<"Richard\n"; else cout<<"Louise\n"; } return 0; }
rishavrrj1 Gawd level _/_
mohitsolanki8391 i can't understand if (setBits(n-1) & 1)
can you explain with example ???sidajwalia mind blown explanation and thinking process. Thank you very much.
subhajit104 can you explain plz ?
akhilgautam123 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 but why N-1 ?
mayank7577 can you please explain the logic how you arrived to this approach, I am not able to visualise the scenario.
balajilitsv 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 Can someone please explain what is happening in the
if (setBits(n-1) & 1)
part of the code???
Dick_Grayson That's great code right there
shreyas_keote 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 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 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 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 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 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 #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 writing N-- was a clever trick, thumbs up.
eshantandon Hi Guys, I just submitted a code and it has been running for 10 mins. Can someone please kill the job?
-Thanks, Eshan
Sig11 Hi Admin, My Submissions are also running for past 20 hrs[Processing] !! Can u pls kill it ?
Thanks Vinish
competitivecoder @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/counter-game/submissions/code/12392799
shraddha416 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=n-pow(2,int(f)); else n=n/2; count++; } if(count%2!=0) cout<<"Louise"<<endl; else cout<<"Richard"<<endl; } return 0;}
pruhujatra 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 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 #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> unsigned int isPowerOfTwo(unsigned long long int n) { return (n && (!(n & (n-1)))); } unsigned long long int largestPowerOfTwo(unsigned long long int n) { while(n & (n-1)) { n = n & (n-1); } 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 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=n-pow(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; } }
-
-
weipeng0098 As is mentioned by slashvar1, the answer is quite simple.
int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int q; cin>>q; for(int i=0;i<q;i++){ unsigned long m; cin>>m; int count=0; while(m%2==0){ m=m>>1; count++; } while(m!=1){ if((m&1)==1) count++; m=m>>1; } if(count%2==1) cout<<"Louise"<<endl; else cout<<"Richard"<<endl; } return 0; }
bazuka_ #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 & (n-1)) { n = n & (n-1); } //n=n&(n-1); 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; }
can you explain me please why my code is not working?
manisha_ringe Please explain.
manisha_ringe What data type can I use for 'm' here in java?
Sort 223 Discussions, By:
Please Login in order to post a comment