Misère Nim HackerRank Solution

Misère Nim HackerRank Solution

In this Misère Nim HackerRank solution, Two people are playing game of Misère Nim. The basic rules for this game are as follows:

  • The game starts with  piles of stones indexed from  to . Each pile  (where ) has  stones.
  • The players move in alternating turns. During each move, the current player must remove one or more stones from a single pile.
  • The player who removes the last stone loses the game.

Given the value of  and the number of stones in each pile, determine whether the person who wins the game is the first or second person to move. If the first player to move wins, print First on a new line; otherwise, print Second. Assume both players move optimally.

Example

In this case, player 1 picks a pile, player 2 picks a pile and player 1 has to choose the last pile. Player 2 wins so return Second.

There is no permutation of optimal moves where player 2 wins. For example, player 1 chooses the first pile. If player 2 chooses 1 from another pile, player 1 will choose the pile with 2 left. If player 2 chooses a pile of 2, player 1 chooses 1 from the remaining pile leaving the last stone for player 2. Return First.

Function Description

Complete the misereNim function in the editor below.

misereNim has the following parameters:

  • int s[n]: the number of stones in each pile

Returns

  • string: either First or Second

Input Format

The first line contains an integer, , the number of test cases.
Each test case is described over two lines:

  1. An integer, , the number of piles.
  2.  space-separated integers, , that describe the number of stones at pile .

Constraints

Sample Input

STDIN   Function
-----   --------
2       T = 2
2       s[] size n = 2
1 1     s = [1, 1]
3       s[] size n = 3
2 1 3   s = [2, 1, 3]

Sample Output

First
Second

Explanation

In the first testcase, the first player removes 1 stone from the first pile and then the second player has no moves other than removing the only stone in the second pile. So first wins.

In the second testcase, the series of moves can be depicted as:

image

In every possible move of first player we see that the last stone is picked by him, so second player wins.

Misère Nim HackerRank Solution

I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.

Problem Solution in C++

string misereNim(vector<int> s) {
int sum = 0;
for(auto  i : s){
    sum += i ;
}
bool allElementsAreOne = ( sum == s.size() ) ? true : false;


if(allElementsAreOne){
    if(s.size()%2 == 0){
        return "First";
    }
    else{
        return "Second";
    }
}
else{
    int xo = 0 ;
    for( int val : s ){
        xo = xo ^ val ;
    }
    if(xo==0){
        return "Second";
    }
    else{
        return "First";
    }
}
}

Problem Solution in JavaScript

function misereNim(s) {
   let sum = s.reduce((a,b) => a + b);
   if(sum == s.length) {
       return s.length % 2 == 0 ? 'First' : 'Second'
   }


    let nimSum = s.reduce((a,b) => a ^ b);
    return nimSum == 0 ? 'Second' : 'First'


}

Problem Solution in Java

 public static String misereNim(List<Integer> s) {
        // Write your code here
        boolean allIsOne = true;
        for (int i : s) {
            if (i != 1) {
                allIsOne = false;
                break;
            }
        }
        Integer res = s.stream().reduce((x, y) -> (x ^ y)).get();
        if (allIsOne) {
            if (s.size() % 2 == 0) return "First";
            else return "Second";
        } else if (res == 0) return "Second";
        else return "First";


    }

Problem Solution in Python

def misereNim(s):
    if(max(s) == 1):
        return "First" if len(s)%2 == 0 else "Second"
       
    xor = reduce((lambda x,y:x ^ y), s)
    return "Second" if xor == 0 else "First"
Solve original Problem on HackerRank here. Checkout more HackerRank Problems