Log inSign up
mediumGeeksforGeeksNot Started

Coin Game Winner

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Two players, A and B, play a turn-based game with n coins. Player A always makes the first move.

On their turn, a player can remove either 1, x, or y coins from the pile (1 < x < y).

The player who takes the last coin wins the game. Assuming both players play optimally, determine whether player A wins the game.

Return true (or A) if player A wins, and false (or B) if player B wins.

### Example 1 - Input: n = 5, x = 3, y = 4 - Output: true (Player A wins) - Explanation: A can remove 4 coins, leaving 1 coin. Now B can only remove 1 coin and wins? Wait, if A removes 4 coins, 1 is left; B removes 1 and wins. But if A removes 1 coin, 4 are left; B can remove 4 and win. If A removes 3 coins, 2 are left; B can only remove 1, leaving 1 coin for A to take and win! Thus, A has a guaranteed winning move (pick 3).

### Example 2 - Input: n = 2, x = 3, y = 4 - Output: false (Player B wins) - Explanation: A can only remove 1 coin (since 2 < 3 and 2 < 4). Then 1 coin remains, which B removes and wins.

Constraints:

  • 1 <= n <= 105
  • 1 < x < y <= 50

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply the fundamental Winning/Losing theorem of combinatorial game theory.
  • Translate minimax decision logic into a linear boolean DP transition.
  • Recognize how rolling windows can reduce memory to O(y).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Two-player zero-sum game with optimal play.
  • Fixed choices of items to remove (1, x, y).
  • Determining if the first player has a winning strategy.

Algorithmic Decision Tree:

  • Define dp[i] = true if current player can force a win with i coins.
  • dp[i] = true if NOT dp[i - 1], NOT dp[i - x], or NOT dp[i - y].

Connected Patterns:

Nim GameStone GamePredict the WinnerDivisor Game

1. Minimax Recursive Search

Intuition

Recursively evaluate whether the current player can force a win by checking if any move forces the opponent to lose.

Algorithm

  1. Define canWin(rem).
  2. If rem == 0, return false.
  3. If !canWin(rem - 1), return true.
  4. If rem >= x and !canWin(rem - x), return true.
  5. If rem >= y and !canWin(rem - y), return true.
  6. Return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5bool canWinRec(int rem, int x, int y) {
6 if (rem == 0) return false;
7 if (!canWinRec(rem - 1, x, y)) return true;
8 if (rem >= x && !canWinRec(rem - x, x, y)) return true;
9 if (rem >= y && !canWinRec(rem - y, x, y)) return true;
10 return false;
11}
12
13int main() {
14 int n = 5, x = 3, y = 4;
15 cout << "Player A wins (Recursive): " << (canWinRec(n, x, y) ? "true" : "false") << endl;
16 return 0;
17}

Time & Space Complexity

  • Time complexity: O(3^n)
  • Space complexity: O(n) recursion call stack

2. Memoized Minimax Search

Intuition

Cache boolean winning states in an array memo of size n + 1.

Algorithm

  1. Create memo array of size n + 1 filled with -1.
  2. Base Case: memo[0] = 0 (losing).
  3. For state rem: if !solve(rem - 1) or (rem >= x && !solve(rem - x)) or (rem >= y && !solve(rem - y)), return memo[rem] = 1.
  4. Otherwise return memo[rem] = 0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int memoSolve(int rem, int x, int y, vector<int>& memo) {
7 if (rem == 0) return 0;
8 if (memo[rem] != -1) return memo[rem];
9
10 if (!memoSolve(rem - 1, x, y, memo)) return memo[rem] = 1;
11 if (rem >= x && !memoSolve(rem - x, x, y, memo)) return memo[rem] = 1;
12 if (rem >= y && !memoSolve(rem - y, x, y, memo)) return memo[rem] = 1;
13 return memo[rem] = 0;
14}
15
16bool canWinMemo(int n, int x, int y) {
17 vector<int> memo(n + 1, -1);
18 return memoSolve(n, x, y, memo) == 1;
19}
20
21int main() {
22 int n = 5, x = 3, y = 4;
23 cout << "Player A wins (Memoized): " << (canWinMemo(n, x, y) ? "true" : "false") << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n) memo table and call stack

3. Bottom-Up Iterative Boolean DP

Intuition

Construct a boolean array dp of size n + 1 filled iteratively from 1 to n.

Algorithm

  1. Create boolean array dp of size n + 1 initialized to false.
  2. dp[0] = false.
  3. For i = 1 to n:
  4. If !dp[i - 1]: dp[i] = true
  5. Else if i >= x && !dp[i - x]: dp[i] = true
  6. Else if i >= y && !dp[i - y]: dp[i] = true
  7. Else: dp[i] = false
  8. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6bool canWinOptimal(int n, int x, int y) {
7 vector<bool> dp(n + 1, false);
8 dp[0] = false;
9
10 for (int i = 1; i <= n; i++) {
11 if (!dp[i - 1]) {
12 dp[i] = true;
13 } else if (i >= x && !dp[i - x]) {
14 dp[i] = true;
15 } else if (i >= y && !dp[i - y]) {
16 dp[i] = true;
17 } else {
18 dp[i] = false;
19 }
20 }
21 return dp[n];
22}
23
24int main() {
25 int n = 5, x = 3, y = 4;
26 cout << "Player A wins (Optimal DP): " << (canWinOptimal(n, x, y) ? "true" : "false") << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n) boolean array

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Minimax RecursiveO(3^n)O(n)Full game tree branch evaluation.Re-evaluates game subtrees
2.Memoized MinimaxO(n)O(n)Top-down memoization.Call stack
3.Bottom-Up Boolean DPOptimalO(n)O(n)Iterate 1 to n with 3 lookup checks.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Checking if dp[i - 1] is true (it must be FALSE for the opponent to lose).

Pitfall 2:

Confusing normal play convention (last move wins) with misère play (last move loses).

Crucial Edge Cases to Validate:

  • n = 1: Player A takes 1 and immediately wins (output: true).
  • n < x and n < y: Only move is 1 coin; A wins if n is odd, loses if n is even.
  • n equals x or y: Player A takes all coins in 1 move and wins (output: true).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the formal Game Theory axiom clearly: 'A state is Winning if it has at least one transition to a Losing state; it is Losing if all transitions lead to Winning states.' Interviewers will immediately recognize your mastery of combinatorial games.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.In combinatorial game theory, why is a state defined as a Winning State if AT LEAST ONE transition leads to a Losing State?

Back to DSA Sheet