WOW man! You are a hacker.

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;
}

Nice. Can you explain why the even/oddness of the popcount of n - 1 gives us our answer?

for t in range(input()):

on = sum(b=='1' for b in bin(input()-1)[2:])

if on&1:
    print "Louise"
else:
    print "Richard"

Nice Explanation

Amazing technique and also explained very well!!

How can I include my own defined library in hackerrank.

but how

if we dont use unsignedit is giving wrong answer... why?

Can you explain how you came up with the approach? Counting the set bits in N-1 seems totally unrelated

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");

@AbhishekVermaIIT

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.

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..

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

Thanks for this genius solution. I am absolutely blown away with this solution,

I have just seen magic!! Thanks for such a nice solution and explaination. It clears some basic concepts of bit magic!!

why does long long give wrong answer,whereas unsigned long long passes all the test cases?

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;
}

Hey Abhishek, can you please explain how you come up with that "counting set-bits in binary representation of N-1" concept....

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;
}

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

Congrats. **#AbhishekVermaIIT **can you explain how that bit manipulation works.

can u explain ur setBits function i am not familiar with bit manipulation??

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

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])

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!

Its a very intelligent way to do this program. Your explanation below was very helpful. Thanks.

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;
}

WOW! Perfect use of Brian Kernighan’s Algorithm. Hats off to you buddy...

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')

The setBits function uses Brian Kernighan’s algorithm to count the number of set bits.

wonderful Solution Bro ...! ;-)

Nice innovative solution :)

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 and n - 1.

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;
}

Gawd level _/_

i can't understand if (setBits(n-1) & 1)
can you explain with example ???

mind blown explanation and thinking process. Thank you very much.

can you explain plz ?

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.

but why N-1 ?

can you please explain the logic how you arrived to this approach, I am not able to visualise the scenario.

Can you explain the mathematical or pratical reason behind this solution? I'm little bit confused on how your solution gives the correct answer.

Can someone please explain what is happening in the

if (setBits(n-1) & 1)

part of the code???

That's great code right there

can you please explain why you subtracted n by 1?

Using 101010101010 as n in n & (n -1) returns a negative which means the while loop will never end. I don't think this answer works for all conditions.

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

yes shreyas i too experienced the same prob .. coz if its an even exponent then richard wins and viceversa .. but the test cases contradict

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

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?

writing N-- was a clever trick, thumbs up.

Hi Admin, My Submissions are also running for past 20 hrs[Processing] !! Can u pls kill it ?

Thanks Vinish

Hi @ Sig11,

your submission has been processed. Please have a look.