Introduction to Nim Game

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

1. The game starts with a number of piles of stones. The number of stones in each pile may not be equal.

2 . The players alternately pick up 1 or more stones from the pile

3. The player to remove the last stone wins.

Example:

Input:  pile= {2,1,4}
Output: First

Approach

Java

public class NimGame {
    public static void main(String[] args) {

        int[] pile = { 2, 1, 4 };

        System.out.println(nimGame(pile));

    }

    static String nimGame(int[] pile) {
        int res = pile[0];
        for (int i = 1; i < pile.length; i++)
            res = res ^ pile[i];
        if (res != 0)
            return "First";
        return "Second";
    }

}

C++

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

string nimGame(vector<int> pile)
{
    int res = pile[0];
    for (int i = 1; i < pile.size(); i++)
        res = res ^ pile[i];
    if (res != 0)
        return "First";
    return "Second";
}

int main()
{

    vector<int> pile = {2, 1, 4};

    cout << nimGame(pile);

    return 0;
}