Nim Game


  • 0

    Click here to see the full article post


  • 0
    Y

    return (n&3) is better , i think ...but why time is same? who can tell me , thank you!


  • 0
    L

    @yake For example, the binary presentation of 4 is 100, 8 is 1000..., which means the last two bits is always 0 if the number is 4's multiples. So n & 3 (n & 11) is for checking if the number is 4's multiples, and that is the result, too.


  • -1
    A

    How is it even possible for other solutions to take lesser time than my solution? Mine beats only 11.73% of the submissions?

    I just did return(n&3). :'(


  • 0
    H

    Because you are not alone with that solution guys))


  • 0
    B

    @yake: Compiler will probably optimize that anyway. In that case, I rather use the remainder which would be more clear.


  • -1
    M
    This post is deleted!

  • 0
    T

    C++ Solution:

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


  • 0
    Z

    who ever began with a multiple of four will lose.


  • 0
    B

    If there are 8 stones,
    I can pick 3
    Opponent can pick 3
    I can pick 2 stones .
    I win. So how is this solution valid.


  • 0
    S

    @bdsh_14 In this question, both of you and your friend are very clever and have optimal strategies for the game. So if you pick 3, the opponent will pick 2 then you will lose.


  • 0
    A

    @bdsh_14
    If there are 8 stones and it's your turn you lose.

    • If you take 3, Opponent will take 1 to force you to have n = 4 and lose next turn.
    • If you take 2, Opponent will take 2 to force you to have n = 4 and lose next turn.
    • If you take 1, Opponent will take 3 to force you to have n = 4 and lose next turn.

    This occurs for every multiple of 4. For example if there are 12 stones:

    • If you take 3, Opponent will take 1 to force you to have n = 8 which we already know is a losing condition.
    • If you take 2, Opponent will take 2 to force you to have n = 8 which we already know is a losing condition.
    • If you take 1, Opponent will take 3 to force you to have n = 8 which we already know is a losing condition.

Log in to reply
 

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