In Game of Nim, two players take turns removing objects from heaps or the pile of stones.

Suppose two players A and B are playing the game. Each is allowed to take only one stone from the pile. The player who picks the last stone of the pile will win the game. Given **N** the number of stones in the pile, the task is to find the winner, if player A starts the game.

**Examples :**

Input : N = 3. Output : Player A Player A remove stone 1 which is at the top, then Player B remove stone 2 and finally player A removes the last stone. Input : N = 15. Output : Player A

For N = 1, player A will remove the only stone from the pile and wins the game.

For N = 2, player A will remove the first stone and then player B remove the second or the last stone. So player B will win the game.

So, we can observe player A wins when N is odd and player B wins when N is even.

Below is the implementation of this approach:

## C++

`// C++ program for Game of Nim with removal ` `// of one stone allowed. ` `#include<bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// Return true if player A wins, ` `// return false if player B wins. ` `bool` `findWinner(` `int` `N) ` `{ ` ` ` `// Checking the last bit of N. ` ` ` `return` `N&1; ` `} ` ` ` `// Driven Program ` `int` `main() ` `{ ` ` ` `int` `N = 15; ` ` ` `findWinner(N)? (cout << ` `"Player A"` `;): ` ` ` `(cout << ` `"Player B"` `;); ` ` ` `return` `0; ` `} ` |

## Java

`// JAVA Code For Game of Nim with ` `// removal of one stone allowed ` `import` `java.util.*; ` ` ` `class` `GFG { ` ` ` ` ` `// Return true if player A wins, ` ` ` `// return false if player B wins. ` ` ` `static` `int` `findWinner(` `int` `N) ` ` ` `{ ` ` ` `// Checking the last bit of N. ` ` ` `return` `N & ` `1` `; ` ` ` `} ` ` ` ` ` `/* Driver program to test above function */` ` ` `public` `static` `void` `main(String[] args) ` ` ` `{ ` ` ` `int` `N = ` `15` `; ` ` ` `if` `(findWinner(N)==` `1` `) ` ` ` `System.out.println(` `"Player A"` `); ` ` ` `else` ` ` `System.out.println(` `"Player B"` `); ` ` ` ` ` `} ` `} ` ` ` `// This code is contributed by Arnav Kr. Mandal. ` |

## Python3

`# Python3 code for Game of Nim with ` `# removal of one stone allowed. ` ` ` `# Return true if player A wins, ` `# return false if player B wins. ` `def` `findWinner( N ): ` ` ` ` ` `# Checking the last bit of N. ` ` ` `return` `N & ` `1` ` ` `# Driven Program ` `N ` `=` `15` `print` `(` `"Player A"` `if` `findWinner(N) ` `else` `"Player B"` `) ` ` ` `# This code is contributed by "Sharad_Bhardwaj". ` |

## C#

`// C# Code For Game of Nim with ` `// removal of one stone allowed ` `using` `System; ` ` ` `class` `GFG { ` ` ` ` ` `// Return true if player A wins, ` ` ` `// return false if player B wins. ` ` ` `static` `int` `findWinner(` `int` `N) ` ` ` `{ ` ` ` `// Checking the last bit of N. ` ` ` `return` `N & 1; ` ` ` `} ` ` ` ` ` `/* Driver program to test above function */` ` ` `public` `static` `void` `Main() ` ` ` `{ ` ` ` `int` `N = 15; ` ` ` ` ` `if` `(findWinner(N) == 1) ` ` ` `Console.Write(` `"Player A"` `); ` ` ` `else` ` ` `Console.Write(` `"Player B"` `); ` ` ` ` ` `} ` `} ` ` ` `// This code is contributed by vt_m. ` |

## PHP

`<?php ` `// PHP program for Game of ` `// Nim with removal of one ` `// stone allowed. ` ` ` `// Return true if player A wins, ` `// return false if player B wins. ` `function` `findWinner(` `$N` `) ` `{ ` ` ` `// Checking the last bit of N. ` `return` `$N` `&1; ` `} ` ` ` `// Driver Code ` `$N` `= 15; ` ` ` `if` `(findWinner(` `$N` `)) ` `echo` `"Player A"` `; ` `else` `echo` `"Player B"` `; ` ` ` `// This code is contributed by vt_m. ` `?> ` |

**Output :**

Player A

**Time Complexity: **O(1).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments