Misère Nim

Two people are playing a game of Misère Nim. The basic rules for this game are as follows:

• The game starts with n piles of stones indexed from 0 to n-1. 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 n 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:

Input:  n = 3, s = {2, 1, 3}
Output: Second

Approach

C++

#include <bits/stdc++.h>
using namespace std;

string misereNim(vector<int> s)
{
    int n = s.size();
    int xr = 0;
    int sum = 0;

    for (int i = 0; i < n; i++)
    {
        xr ^= s[i];
        sum += s[i];
    }

    if (n % 2 == 0)
    {
        return n != sum && xr == 0 ? "Second" : "First";
    }
    else
    {
        return n == sum || xr == 0 ? "Second" : "First";
    }
}

int main()
{

    int n = 3;
    vector<int> s = {2, 1, 3};

    cout << misereNim(s) << "\n";
    return 0;
}