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.
This challenge is poorly written. Here's a better explanation.
In (this version of) the game of Nim, whoever takes the last stone wins. On your turn, you can take as many stones as you want from any single pile. You have to take at least one stone on your turn (you cannot pass). It is a well known result in game theory that if both players play optimally, then the winner is decided by the following property. On your turn let p be the number of piles, let size[i] be the number of stones currently in pile i. If size[1] XOR size[2] XOR size[3] ... XOR size[p] != 0, then it is possible for you to make a move that forces your opponent to lose (eventually). If that XOR is 0, then no matter what you do, the opponent (if they play optimally) can make a move that forces you to lose (eventually).
This challenge wants the number of initial setups such that the first player can force a win, with one extra condition: at the start of the game no two piles have the same number of stones.
So, you want to count the number of ways to take n distinct integers from [1, 2^m-1] such that the XOR of those n values is not zero.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Tastes Like Winning
You are viewing a single comment's thread. Return to all comments →
This challenge is poorly written. Here's a better explanation.
In (this version of) the game of Nim, whoever takes the last stone wins. On your turn, you can take as many stones as you want from any single pile. You have to take at least one stone on your turn (you cannot pass). It is a well known result in game theory that if both players play optimally, then the winner is decided by the following property. On your turn let
p
be the number of piles, letsize[i]
be the number of stones currently in pilei
. Ifsize[1] XOR size[2] XOR size[3] ... XOR size[p] != 0
, then it is possible for you to make a move that forces your opponent to lose (eventually). If that XOR is 0, then no matter what you do, the opponent (if they play optimally) can make a move that forces you to lose (eventually).This challenge wants the number of initial setups such that the first player can force a win, with one extra condition: at the start of the game no two piles have the same number of stones.
So, you want to count the number of ways to take
n
distinct integers from [1, 2^m-1] such that the XOR of thosen
values is not zero.