LeetCode 292: Nim Game Solution in Python – A Step-by-Step Guide

What Is LeetCode 292: Nim Game?

In LeetCode 292: Nim Game, you’re given an integer n representing a pile of stones. You and your opponent take turns removing 1, 2, or 3 stones, and the player who removes the last stone wins. You go first, and both of you play perfectly—always making the smartest move. Your task is to figure out if you can win with n stones. For example, with 4 stones, you lose because no matter how many you take, your opponent can force a win. This problem tests your ability to spot patterns, sharing a vibe with game theory puzzles like LeetCode 877: Stone Game.

Problem Statement

• Input: An integer n (number of stones).
• Output: True if you can win, False if you can’t.
• Rules: Remove 1, 2, or 3 stones per turn; you start; last to remove wins; optimal play.

Constraints

• n: 1 to 2³¹ - 1 (big numbers possible).

Examples

• Input: n = 4
• Output: False
• Input: n = 1
• Output: True
• Input: n = 7
• Output: True

Understanding the Problem: Can You Win?

To solve LeetCode 292: Nim Game in Python, we need to determine if you, going first, can force a win with n stones, assuming both players pick the best moves. With 1 stone, you take it and win—easy! With 4, though, every move you make (1, 2, or 3) leaves stones for your opponent to finish off. There’s a pattern here, and we’ll crack it with:

• Best Solution (Mathematical Pattern): O(1) time, O(1) space—super quick.
• Alternative Solution (Dynamic Programming): O(n) time, O(n) space—more complex.

Let’s dive into the math solution with a friendly breakdown that’s easy to follow.

Best Solution: Mathematical Pattern

Why This Is the Best Solution

The mathematical pattern solution is the star for LeetCode 292 because it’s lightning fast—O(1) time—and uses O(1) space, needing no loops or extra storage. It boils down to a simple rule based on the number 4, which we’ll uncover by playing a few rounds. It’s like finding a secret cheat code that tells you instantly if you’ll win—perfect for this game!

How It Works

Let’s play this game like we’re figuring it out together:

• Step 1: Try Small Numbers:
• 1 stone: You take 1, win—True.
• 2 stones: You take 2, win—True.
• 3 stones: You take 3, win—True.
• 4 stones:
• Take 1 → 3 left, opponent takes 3, wins.
• Take 2 → 2 left, opponent takes 2, wins.
• Take 3 → 1 left, opponent takes 1, wins.
• You lose—False!
• Step 2: Keep Going:
• 5 stones: Take 1 → 4 left, opponent can’t win (from 4, you win), so you win—True.
• 6 stones: Take 2 → 4 left, opponent loses, you win—True.
• 7 stones: Take 3 → 4 left, opponent loses, you win—True.
• 8 stones:
• Take 1 → 7, opponent takes 3 → 4, you lose.
• Take 2 → 6, opponent takes 2 → 4, you lose.
• Take 3 → 5, opponent takes 1 → 4, you lose.
• False again!
• Step 3: Spot the Pattern:
• Win: 1, 2, 3, 5, 6, 7.
• Lose: 4, 8.
• Notice: You lose when n is a multiple of 4 (4, 8, 12...). Why? If n = 4k, every move leaves your opponent with a non-multiple (4k-1, 4k-2, 4k-3), and they can force it back to 4(k-1), eventually 0—you lose.
• Step 4: The Rule:
• If n % 4 == 0 (divisible by 4), you lose—False.
• If n % 4 != 0 (1, 2, or 3 leftover), you win—True.
• Step 5: Why It Works:
• With optimal play, you can always leave your opponent with a multiple of 4 if n isn’t one, forcing them to lose.
• If n is a multiple of 4, they can do the same to you.

It’s like a magic number trick—4 decides your fate!

Step-by-Step Example

Example: n = 7

• 7 % 4 = 3 (not 0).
• Not divisible by 4 → you can win.
• Play: Take 3 → 4 left, opponent takes any, you finish—True.

Example: n = 4

• 4 % 4 = 0.
• Divisible by 4 → you lose.
• Play: Any move (1, 2, 3), opponent takes rest—you lose—False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy codeclass Solution:
    def canWinNim(self, n: int) -> bool:
        # Step 1: Check if n is divisible by 4
        return n % 4 != 0  # True if you win, False if you lose

• Line 4: Use the modulo operator (%) to see if n divides evenly by 4.
• If n % 4 != 0 (like 1, 2, 3), return True—you can win.
• If n % 4 == 0 (like 4, 8), return False—you can’t.
• That’s it—one line!

• Time Complexity: O(1)—just a quick math check.
• Space Complexity: O(1)—no extra space needed.

This is like a secret handshake—fast and simple!

Alternative Solution: Dynamic Programming

Why an Alternative Approach?

Dynamic programming (DP) builds a table to track winning positions—O(n) time, O(n) space. It’s overkill for this problem since the math trick works instantly, but it’s a fun way to see the game unfold step-by-step, like mapping out every move to confirm the pattern.

How It Works

Let’s imagine we’re building a win chart:

• Step 1: Set up a list dp where dp[i] is True if you win with i stones, False if you lose.
• Step 2: Base cases:
• 0 stones: False (you lose, nothing to take).
• 1, 2, 3 stones: True (you take all, win).
• Step 3: Build up:
• For each i > 3, you win if any move (i-1, i-2, i-3) leaves your opponent losing (dp[i-1], dp[i-2], dp[i-3] = False).
• Step 4: Check n in the chart.

It’s like making a playbook for every pile size!

Step-by-Step Example

Example: n = 5

• DP Setup: dp = [False, True, True, True, ?, ?].
• i=4: dp[3], dp[2], dp[1] all True → dp[4] = False.
• i=5: dp[4] = False → dp[5] = True (take 1, opponent loses).
• Result: dp[5] = True.

Code for Dynamic Programming Approach

Copy codeclass Solution:
    def canWinNim(self, n: int) -> bool:
        if n <= 0:
            return False

        dp = [False] * (n + 1)  # Winning status for 0 to n stones
        dp[1] = True  # 1 stone, you win
        if n >= 2:
            dp[2] = True  # 2 stones, you win
        if n >= 3:
            dp[3] = True  # 3 stones, you win

        for i in range(4, n + 1):
            # Win if any move leaves opponent losing
            dp[i] = not (dp[i-1] and dp[i-2] and dp[i-3])

        return dp[n]

• Time Complexity: O(n)—builds up to n.
• Space Complexity: O(n)—stores the dp array.

It’s a detailed map, but we don’t need it here!

Comparing the Two Solutions

• Math Pattern (Best):
• Pros: O(1) time, O(1) space, instant answer.
• Cons: Needs pattern insight.
• DP (Alternative):
• Pros: O(n) time, O(n) space, shows the logic.
• Cons: Overkill, slower, more space.

Math wins by a landslide.

Additional Examples and Edge Cases

• n = 1: True.
• n = 8: 8 % 4 = 0 → False.
• n = 3: True.

Both work, but math’s faster.

Complexity Breakdown

• Math: Time O(1), Space O(1).
• DP: Time O(n), Space O(n).

Math is the champ.

Key Takeaways

• Math: Patterns beat loops—cool!
• DP: Build it up—detailed but heavy!
• Games: Strategy is fun.
• Python Tip: Math and lists shine—see [Python Basics](/python/basics).

Final Thoughts: Win the Game

LeetCode 292: Nim Game in Python is a playful logic challenge. The math solution is a quick win, while DP shows the full play-by-play. Want more? Try LeetCode 877: Stone Game or LeetCode 486: Predict the Winner. Ready to play? Head to Solve LeetCode 292 on LeetCode and grab that victory today!