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 )$, B will always have the advantage. Therefore, A's winning strategy is based on the remainder when $( N )$ is divided by 5.

• If $( 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 \neq 0 )$, A should pick $( N \% 5 )$ matchsticks to leave B with a multiple of 5 matchsticks, ensuring A's winning position.

• Game Theory

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

JavaScript

Written by @manishh12

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

TypeScript

Written by @manishh12

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

 

Python

Written by @manishh12

 def matchGame(N):
     return -1 if N % 5 == 0 else N % 5

Java

Written by @manishh12

 public class Solution {
     public int matchGame(long N) {
         return N % 5 == 0 ? -1 : (int)(N % 5);
     }

    
 }

C++

Written by @manishh12

 #include <iostream>

 using namespace std;

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

 

Complexity Analysis

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

tip

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

References

• GeeksforGeeks Problem: GeeksforGeeks Problem
• GeeksforGeeks Problem: GeeksforGeeks solution
• Solution Author: Manish Kumar Gupta

---