We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Algorithms
  3. Game Theory
  4. Introduction to Nim Game

Introduction to Nim Game

Nim is the most famous two-player algorithm game. The basic rules for this game are as follows:

  • The game starts with a number of piles of stones. The number of stones in each pile may not be equal.
  • The players alternately pick up or more stones from pile
  • The player to remove the last stone wins.

For example, there are piles of stones having stones in them. Play may proceed as follows:

Player  Takes           Leaving
                        pile=[3,2,4]
1       2 from pile[1]  pile=[3,4]
2       2 from pile[1]  pile=[3,2]
1       1 from pile[0]  pile=[2,2]
2       1 from pile[0]  pile=[1,2]
1       1 from pile[1]  pile=[1,1]
2       1 from pile[0]  pile=[0,1]
1       1 from pile[1]  WIN

Given the value of and the number of stones in each pile, determine the game's winner if both players play optimally.

Function Desctription

Complete the nimGame function in the editor below. It should return a string, either First or Second.

nimGame has the following parameter(s):

  • pile: an integer array that represents the number of stones in each pile

Input Format

The first line contains an integer, , denoting the number of games they play.

Each of the next pairs of lines is as follows:

  1. The first line contains an integer , the number of piles.
  2. The next line contains space-separated integers , the number of stones in each pile.

Constraints

  • Player 1 always goes first.

Output Format

For each game, print the name of the winner on a new line (i.e., either First or Second).

Sample Input

2
2
1 1
3
2 1 4

Sample Output

Second
First

Explanation

In the first case, there are piles of stones. Player has to remove one pile on the first move. Player removes the second for a win.

In the second case, there are piles of stones. If player removes any one pile, player can remove all but one of another pile and force a win. If player removes less than a pile, in any case, player can force a win as well, given optimal play.