Question

292. Nim Game

中文文档

Description

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 = 4
Output: false
Explanation: 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 = 1
Output: true

Example 3:

Input: n = 2
Output: true

 

Constraints:

• 1 <= n <= 231 - 1

Solutions

Solution 1: Finding the Pattern

The first player who gets a multiple of $4$ (i.e., $n$ can be divided by $4$) will lose the game.

Proof:

1. When $n \lt 4$, the first player can directly take all the stones, so the first player will win the game.
2. When $n = 4$, no matter whether the first player chooses $1, 2, 3$, the second player can always choose the remaining number, so the first player will lose the game.
3. When $4 \lt n \lt 8$, i.e., $n = 5, 6, 7$, the first player can correspondingly reduce the number to $4$, then the "death number" $4$ is given to the second player, and the second player will lose the game.
4. When $n = 8$, no matter whether the first player chooses $1, 2, 3$, it will leave a number between $4 \lt n \lt 8$ to the second player, so the first player will lose the game.
5. …
6. By induction, when a player gets the number $n$, and $n$ can be divided by $4$, he will lose the game, otherwise, he will win the game.

The time complexity is $O(1)$, and the space complexity is $O(1)$.

class Solution:
  def canWinNim(self, n: int) -> bool:
    return n % 4 != 0

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

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

func canWinNim(n int) bool {
  return n%4 != 0
}

function canWinNim(n: number): boolean {
  return n % 4 != 0;
}

impl Solution {
  pub fn can_win_nim(n: i32) -> bool {
    n % 4 != 0
  }
}