JAVA Solution if n = 4 * k it will be false else it will be True; with DP explanation


  • 0
    T

    First we will find n = 1,2,3 it is true,then we begin analyze:
    4 = 1+3;2+2; 3+1 so whatever we choose it will lose 1,or 2 or 3 with the second one to choose, from former analyse it must be winner, so I will be loser.
    5 = 1 + 4; 2 + 3; 3 + 2, 4 + 1; so if I choose 1 the dp[n - 1] = fasle means the second one must be loser I will be winner.
    ...but if it is 8 then whatever I choose the second one will make it sum of 4. then the game become 4 stones game, we have analyse before I will be loser.
    ...12: the same he can make the game become 8 stones game we have analysed before I will be loser.
    ....
    so only if n % 4 == 0 I must lose, and other number I have the way to win.

     public boolean canWinNim(int n) {
            if (n <= 3) {
                return true;
            }
            if (n % 4 == 0) {
                return false;
            }
            return true;
        }
    

Log in to reply
 

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