hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Game of Nim


  • Approach:

    1. The very famous Nim game incorporates taking an optimal amount of stones from the given piles so that both players can win.

    2. Traverse through the given array.

    3. Take the XOR of the given array.

    4. If the XOR is zero then Bob wins. Return False.

    5. If not then Alice wins. Return True.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(1)


Code [C++]

bool nimGame(vector<int> &piles){

int xor = 0;

for(int i=0; i<piles.size(); i++){

xor = xor ^ piles[i];

}

return (xor == 0);

}