Short and concise C++ solution with explanation


  • 9
    A

    Idea is very simple. Lets build the "win-lose" strategy. If we can from our current position go to the "lose" position then current position is 'win', else it is 'win' position for friend. So the 'win-lose' strategy looks like this:

    1 => 'w' (we can remove 1 stone)

    2 => 'w' (we can remove 2 stones)

    3 => 'w' (we can remove 3 stones)

    4 => 'l' (no matter how many stones we remove next position(1, 2 or 3) will be 'w' for friend)

    5 => 'w' (we can remove 1 stone and move to 'l'-position)

    6 => 'w'

    7 => 'w'

    8 => 'l'

    9 => 'w'

    10 => 'w'

    11 => 'w'

    11 => 'l'

    ....

    It's easy to see, that every fourth position is 'lose'. So the answer is (n % 4 != 0).
    Here the code:

    class Solution {
    public:
        bool canWinNim(int n) 
        {
            return (n % 4);
        }
    };

  • 0
    G

    looks good, except your explanation for position 5. It's a win because you would remove 1 stone, putting your opponent in the lose state (4 stones remaining).


  • 0
    A

    Thanks) just missed it


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.