Nim Game Python Solution with Tests

LeetCode 292, Easy. Topics: Math, Brainteaser, Game Theory. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 20 parametrized pytest cases, and a playground notebook:

lcpy gen -n 292   # by problem number
lcpy gen -s nim_game   # by problem name

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.

Examples

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.

Input: n = 1
Output: true

Input: n = 2
Output: true

Constraints

1 <= n <= 2^31 - 1

Follow up: Could you solve it with a closed-form solution instead of a DP?

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(1)
    # Space: O(1)
    def can_win_nim(self, n: int) -> bool:
        return n % 4 != 0

Complexity

Time	Space
O(1)	O(1)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Nim Game Python Solution with Tests

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags