Simple Solution Scalable for different stones O(1)


  • 0
    B

    In order to tackle this problem, we can look at the base case, considering that you always move first.
    1 Stone: you remove it, you win.
    2 Stones: remove both, win
    3 stones: remove three, win
    4 stones: removing any number causes your opponent to win.
    5 stones: remove one, and win
    6 stones: remove two, and win
    7 stones: remove three, and win
    8 stones: removing any number causes your opponent to remove enough to reach 4, and ultimately causes you to lose.
    ...
    From this, you can see that whenever it is your turn and there are four stones left, you will lose. Otherwise, you will win. This can just be set as n % 4 != 0 (n modulus 4, obtaining the remainder after you divide the number of stones by 4), and checking if the boolean comparison returns true or false.

    The x below is scalable for different NIM game number of stones removed; x = total stones removable + 1; Anything above the range that you can remove.
    For example, if each of you can remove up to 5 stones each, then x = 6. In this case, you would win whenever n %6 != 0;

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

Log in to reply
 

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