1 line 0 ms C++ solution with mathematic explanation


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

    Let's look at the basic case. If 1 or 2 or 3 stones left and it's my turn, I'm gonna win.

    So how to guarantee this "win" status? That must be 4 stones left when it's my friend's turn. Because 4 - 1 = 3, 4 - 2 = 2, 4 - 3 = 1.

    How to give the "lose" status to my friend? That must be 5 or 6 or 7 stones left when it's my turn. Becuase we have the chance to make the count of left stones be 4: 5 - 1 = 4, 6 - 2 = 4, 7 - 3 = 4. Then You may find 5 = 1 + 4, 6 = 2 + 4, 7 = 3 + 4. Wow, 1, 2, 3 are our basic cases.

    Let's go on. How to guarantee the "win" status of "5 or 6 or 7 stones left when it's my turn"? We should give the "lose" status to my friend that is "8 stones left when it's my friend's turn".Because 8 - 1 = 7, 8 - 2 = 6, 8 - 3 = 5. Again, how to give the "lose" status to my friend? We must be at status of 9, 10, 11 stones left when it's my turn. Because then we have the chance to make the count of left stones be 8: 9 - 1 = 8, 10 - 2 = 8, 11 - 3 = 8. We can find 9 = 1 + 8 = (1 + 4) + 4 = 5 + 4, 10 = 2 + 8 = (2 + 4) + 4 = 6 + 4, 11 = (3 + 4) + 4 = 7 + 4. The formula is now going out: T(n) = T(n - 1) + 4. T(n) is the left stones of the n times of my turn. The basic case T(0) = {1, 2, 3}.

    Now we can write a solution like: Test if the number is one of T(n). If yes, we can win. Otherwise we'd lose. Actually it takes O(n) time complexity.

    The above solution is really slow to this problem and will lead to a "Time Limit Exceeded" complain.How can we optimize it? Let's expand the formula T(n) = T(n - 1) + 4:

    T(n) = {(((1 + 4) + 4) + 4 ..., ((2 + 4) +4) + 4 ..., ((3 + 4) +4) + 4 ...}
    = {1 + 4n, 2 + 4n, 3 + 4*n}

    Can you get the idea? If T(n) % 4 is 1 or 2 or 3, we can win the game. And beacuse the mod value can only be 0, 1, 2 or 3, that implies if T(n) % 4 != 0, we'll win the game. Now we get the one liner:

     return n % 4 != 0;
    

    Happy coding :)


Log in to reply
 

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