Nimble Game

Two people are playing Nimble! The rules of the game are:

• The game is played on a line of n squares, indexed from 0 to n-1. Each square  (where ) contains  coins.
  
• The players move in alternating turns. During each move, the current player must remove exactly the coin from square i and move it to square j if and only if .
• The game ends when all coins are in square 0 and nobody can make a move. The first player to have no available move loses the game.

Given the value of n and the number of coins in each square, determine whether the person who wins the game is the first or second person to move. Assume both players move optimally.

Example:

Input:  n = 5, s = {0, 2, 3, 0, 6}
Output: First

Approach

C++

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

string nimbleGame(vector<int> s)
{
    int n = s.size();
    int r = 0;
    for (int i = 0; i < n; i++)
        if (s[i] & 1)
            r ^= i;
    if (r == 0)
        return "Second";
    else
        return "First";
}

int main()
{

    int n = 5;
    vector<int> s = {0, 2, 3, 0, 6};

    cout << nimbleGame(s) << "\n";

    return 0;
}