C solution and detail explanation


  • 0
    J

    key point :
    1.whoever can leave 4 stone behind, can win this game.
    e.g : Total 5 stone, A take #1 and leave 4 behind. no matter B take 1/2/3 stone, A can take the final one stone(#5).
    2.Accoring to 1, if you can take stone #(N-4) in N stones, you will leave 4 stone behind and win the game.
    3.Accoring to 2, if you can take steon #((N-4)-4), you will win
    4.Accoring to 1&2&3, "if there exist a number X, which N-4X = 1 or 2 or 3, you will win"
    5.According to 4, let's change equation "N-4
    X = 1(or 2 or 3)" to "N-1(or 2 or 3) = 4*X"
    then we can derives below code

    bool canWinNim(int n) {
     if((n-1)%4==0 || (n-2)%4==0 || (n-3)%4==0 )
     {
         return true;
     }
     else
     {
        return false;
     }
    }
    

Log in to reply
 

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