What is Nim Game and how it is played?
It is a game in which two players play optimally turn by turn .
-
In each turn a player can choose only one pile and remove any number of stones (at least one) from that pile.
-
The person who is unable to make a move looses , hence the player who makes the last move wins.
-
determine which player wins the game.
How to decide who will win?
To decide who will win the initial configuration of the piles matter.
-
If the xor of all elements of the array is non-zero , then person starting the game will win.
-
If the xor of all elements of the array is zero , then other person will win.
-
Why it works ?
-
if the xor if all elements is zero then if we make any moves , the xor of all elements will definitely become non zero .
Why?
If the xor of all elements is non zero , then we can either make the xor non-zero again , or make the xor zero.
-
There definitely exists atleast one way to make xor zero again.
Why?
How to reach the Conclusion -
Conclusion -
Hence if xor is zero B Wins , else A wins
