Solution and Interpretation


  • 2
    V
      public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
    

    why is n%4 ==0 represent losing the game?
    I figured out two ways to understand.

    • Deduction

    n = 1,2,3,4,5,6,7,8,9,10
    win=t,t,t,F,t,t,t,F,t,t,t,F....

    ( When you get 5, you can make the strategy to "give other 4", and you can always achieve that when n >5 and n<8 . Generally , when n grows, you have 3 winning point after a losing point by "giving out the losing point" )

    • Divide

    Divide the n into n /4 part, and think it n /4 games , you can win the last game ( n - n/4) to let your opponent facing the left game . Because they are all 4-game so he/she would lose them all.


Log in to reply
 

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