Skip to main content

Matchsticks Game

In this page, we will solve the problem of determining the number of matchsticks the first player should pick to guarantee a win in the matchsticks game using different approaches. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, and C++.

Problem Description​

Two friends, A and B, are playing the game of matchsticks. In this game, a group of N matchsticks is placed on the table. The players can pick any number of matchsticks from 1 to 4 (both inclusive) during their chance. The player who takes the last matchstick wins the game. If A starts first, how many matchsticks should he pick on his first turn such that he is guaranteed to win the game, or determine if it's impossible for him to win. Return -1 if it's impossible for A to win the game, else return the number of matchsticks he should pick on his first turn to guarantee a win. Note: Consider both A and B play the game optimally.

Examples​

Example 1:

Input:
N = 48
Output:
3
Explanation:
Player A is guaranteed a win if he picks 3 matchsticks first.

Example 2:

Input:
N = 15
Output:
-1
Explanation:
Player A is guaranteed a loss no matter how many matches he picks at first.

Constraints​

  • 1 <= N <= 10^18

Solution for Matchsticks Game Problem​

Intuition and Approach​

The problem can be solved using game theory and mathematical analysis. The key insight is to notice the pattern based on the modulo operation.

When A starts the game, he needs to ensure that after his turn, the number of matchsticks left is such that B cannot force a win. This means A needs to leave B with a number of matchsticks that is a multiple of 5, because if (N%5=0)( N \% 5 = 0 ), B will always have the advantage. Therefore, A's winning strategy is based on the remainder when (N)( N ) is divided by 5.

  • If (N%5=0)( N \% 5 = 0 ), then no matter how many matchsticks A picks (1 to 4), B can always pick a number of matchsticks to maintain the advantage and eventually win. Hence, it's impossible for A to guarantee a win, and the answer is -1.
  • If (N%5≠0)( N \% 5 \neq 0 ), A should pick (N%5)( N \% 5 ) matchsticks to leave B with a multiple of 5 matchsticks, ensuring A's winning position.

Approach: Game Theory​

The key observation is that if the number of matchsticks ( N ) modulo 5 is 0, then player A will lose if both players play optimally. Otherwise, player A can always pick ( N % 5 ) matchsticks to ensure a win.

Implementation​

Live Editor
function matchGame() {
  const N = 48;

  const matchGame = (N) => {
    return N % 5 === 0 ? -1 : N % 5;
  };

  const result = matchGame(N);
  return (
    <div>
      <p>
        <b>Input:</b> N = {N}
      </p>
      <p>
        <b>Output:</b> {result}
      </p>
    </div>
  );
}
Result
Loading...

Codes in Different Languages​

Written by @manishh12
 function matchGame(N) {
return N % 5 === 0 ? -1 : N % 5;
}


Complexity Analysis​

  • Time Complexity: O(1)O(1)
  • Space Complexity: O(1)O(1)
tip

The key insight is recognizing the modulo operation's role in determining the game's outcome.

References​