Counter Game problem HackRank

 Louise and Richard have developed a numbers game. They pick a number and check to see if it is a power of . If it is, they divide it by . If not, they reduce it by the next lower number which is a power of . Whoever reduces the number to  wins the game. Louise always starts.

Given an initial value, determine who wins the game.

Example

It's Louise's turn first. She determines that  is not a power of . The next lower power of  is , so she subtracts that from  and passes  to Richard.  is a power of , so Richard divides it by  and passes  to Louise. Likewise,  is a power so she divides it by  and reaches . She wins the game.

Update If they initially set counter to , Richard wins. Louise cannot make a move so she loses.

Function Description

Complete the counterGame function in the editor below.

counterGame has the following parameter(s):

int n: the initial game counter value

Returns

string: either Richard or Louise

Input Format

The first line contains an integer , the number of testcases.

Each of the next  lines contains an integer , the initial value for each game.

Constraints

Sample Input

1

6

Sample Output

Richard

Explanation

As  is not a power of , Louise reduces the largest power of  less than  i.e., , and hence the counter reduces to .

As  is a power of , Richard reduces the counter by half of  i.e., . Hence the counter reduces to .

As we reach the terminating condition with , Richard wins the game.

Bitwise Approach

import java.io.*;

import java.math.*;

import java.security.*;

import java.text.*;

import java.util.*;

import java.util.concurrent.*;

import java.util.function.*;

import java.util.regex.*;

import java.util.stream.*;

import static java.util.stream.Collectors.joining;

import static java.util.stream.Collectors.toList;

class Result {

    /*

     * Complete the 'counterGame' function below.

     *

     * The function is expected to return a STRING.

     * The function accepts LONG_INTEGER n as parameter.

     */

    public static String counterGame(long n) {

    // Write your code here

int turns = 0;

       

        while (n > 1) {

            if ((n & (n - 1)) == 0) { // Check if n is a power of 2

                n /= 2;

            } else {

                long highestPower = Long.highestOneBit(n); // Find the largest power of 2 less than n

                n -= highestPower;

            }

            turns++;

        }

        return (turns % 2 == 1) ? "Louise" : "Richard";

    }

}

public class Solution {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, t).forEach(tItr -> {

            try {

                long n = Long.parseLong(bufferedReader.readLine().trim());

                String result = Result.counterGame(n);

                bufferedWriter.write(result);

                bufferedWriter.newLine();

            } catch (IOException ex) {

                throw new RuntimeException(ex);

            }

        });

        bufferedReader.close();

        bufferedWriter.close();

    }

}