動機

原來這麼簡單!?

Problem

You are playing the following Nim Game with your friend:

  • Initially, there is a heap of stones on the table.
  • You and your friend will alternate taking turns, and you go first.
  • On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
  • The one who removes the last stone is the winner.

Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.

 

Example 1:

Input: n = 4Output: falseExplanation: These are the possible outcomes:1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.3. You remove 3 stones. Your friend removes the last stone. Your friend wins.In all outcomes, your friend wins.

Example 2:

Input: n = 1Output: true

Example 3:

Input: n = 2Output: true

 

Constraints:

  • 1 <= n <= 231 - 1

Sol

拿走最後一顆的贏，一次最多3顆

如果只有 <=3，那我們會贏 但到了4就會輸，

接著5~7，只要最後留4個，對面就會輸，但8個的話就是我們出事了

所以規律就是(3+1)的倍數

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n%(3+1)