Counter game HackerRank Solution

Counter game HackerRank Solution
Source : https://www.hackerrank.com/challenges/counter-game

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.

As an example, let the initial value . It's Louise's turn so she first 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. It should return the winner's name, either Richard or Louise.

counterGame has the following parameter(s):

• n: an integer to initialize the game counter

Input Format

The first line contains an integer , the number of testcases.
Each of the next lines contains an integer , the initial value for the game.

Constraints

Output Format

For each test case, print the winner's name on a new line in the form Louise or Richard.

Sample Input 0

16

Sample Output 0

Richard

Explanation 0

• is not a power of so Louise reduces it by the largest power of less than :.
• is a power of so Richard divides by to get and wins the game.

Source : https://www.hackerrank.com/challenges/counter-game

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	import java.math.BigInteger;
	// Case 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 turning the most significant 1 in N to 0. This operation will keep
	// repeating until we reach Case 2. To count the number of times we have to do Case 1's operation
	// we can count the number of 1s in our original number (except for the least significant 1).
	// Case 2: If N is a power of 2, we must "reduce the counter by half of N".
	//
	// This is equivalent of doing a right shift. This operation keeps repeating until the game ends.
	// The number of right shifts we do depends on the number of trailing 0s.
	// Additional optimization:
	//
	// Instead of counting the number of times Case 1 and Case 2 happen separately, we can just
	// calculate the number of 1s in N-1. This is because subtracting 1 from our number will turn
	// all of the trailing 0s (which we wanted to count) into 1s that we can count (for example:
	// 10000 would become 01111)
	// Example:
	//
	// 10110100 Case 1
	// 110100 Case 1
	// 10100 Case 1
	// 100 Case 2
	// 10 Case 2
	// 1 Done
	//
	// We had 5 operations total. Directly applying our algorithm would look like this:
	//
	// Original Number: 10110100
	// Number - 1 : 10110011 and the number of 1s is 5
	public class Solution {
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int T = scan.nextInt();
	while (T-- > 0) {
	BigInteger N = new BigInteger(scan.next());
	N = N.subtract(BigInteger.ONE);
	System.out.println(N.bitCount() % 2 == 0 ? "Richard" : "Louise");
	}
	scan.close();
	}
	}