Problem

The Game of Master Mind is played as follows. The computer chooses a code consisting of four colors from {R, Y, G, B}. A player makes a guess (also four colors). For each guess the player is told:

  • hits (correct color in correct position), and
  • pseudo-hits (correct color in wrong position).

Example:

1
2
3
4

Solution: RGGB
Guess:    YRGB
Hits: 2  (positions 3 and 4)
Pseudo-hits: 1 (color R exists but in wrong position)

Return the number of hits and pseudo-hits for a given guess and solution.

Note: LeetCode has a very similar problem titled “Bulls and Cows” (LeetCode 299) which asks for counts of bulls and cows — equivalent to hits and pseudo-hits.

Similar Problems

Solution

We provide two clean approaches: Method 1 uses frequency counts (recommended), Method 2 uses a compact bit-mask idea for small alphabets.

Method 1 — Two-pass frequency counts (recommended)

Intuition

Count exact matches (hits) in one pass. For non-matching positions, count remaining colors in the solution and then match them against the guess to compute pseudo-hits.

Approach

  • Initialize hits = 0, pseudo = 0 and an array cnt[4] for colors {R,Y,G,B}.
  • First pass: for each index i, if guess[i] == solution[i] increment hits; else increment cnt[index_of(solution[i])].
  • Second pass: for each index i where guess[i] != solution[i], if cnt[index_of(guess[i])] > 0 then increment pseudo and decrement that count.
  • Return (hits, pseudo).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
 public:
  pair<int,int> masterMind(const string& guess, const string& solution) {
  auto idx = [](char c){ return c == 'R' ? 0 : c == 'Y' ? 1 : c == 'G' ? 2 : 3; };
  int hits = 0, pseudo = 0;
  int cnt[4] = {0,0,0,0};
  for (size_t i = 0; i < guess.size(); ++i) {
    if (guess[i] == solution[i]) ++hits;
    else ++cnt[idx(solution[i])];
  }
  for (size_t i = 0; i < guess.size(); ++i) {
    if (guess[i] == solution[i]) continue;
    int j = idx(guess[i]);
    if (cnt[j] > 0) { --cnt[j]; ++pseudo; }
  }
  return {hits, pseudo};
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

package main

func idx(c byte) int {
  switch c {
  case 'R': return 0
  case 'Y': return 1
  case 'G': return 2
  default:  return 3
  }
}

func MasterMind(guess, solution string) (int,int) {
  hits, pseudo := 0, 0
  cnt := [4]int{0,0,0,0}
  for i := 0; i < len(guess); i++ {
    if guess[i] == solution[i] { hits++ }
    else { cnt[idx(solution[i])]++ }
  }
  for i := 0; i < len(guess); i++ {
    if guess[i] == solution[i] { continue }
    j := idx(guess[i])
    if cnt[j] > 0 { cnt[j]--; pseudo++ }
  }
  return hits, pseudo
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
  public static class Result { public int hits; public int pseudoHits; }

  private int idx(char c) { return c=='R'?0: c=='Y'?1: c=='G'?2:3; }

  public Result masterMind(String guess, String solution) {
    Result res = new Result();
    int[] cnt = new int[4];
    for (int i = 0; i < guess.length(); i++) {
      if (guess.charAt(i) == solution.charAt(i)) res.hits++;
      else cnt[idx(solution.charAt(i))]++;
    }
    for (int i = 0; i < guess.length(); i++) {
      if (guess.charAt(i) == solution.charAt(i)) continue;
      int j = idx(guess.charAt(i));
      if (cnt[j] > 0) { cnt[j]--; res.pseudoHits++; }
    }
    return res;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
  def master_mind(self, guess: str, solution: str) -> tuple[int,int]:
    def idx(c: str) -> int:
      return 0 if c=='R' else 1 if c=='Y' else 2 if c=='G' else 3
    hits = 0
    pseudo = 0
    cnt = [0,0,0,0]
    for i, ch in enumerate(guess):
      if ch == solution[i]:
        hits += 1
      else:
        cnt[idx(solution[i])] += 1
    for i, ch in enumerate(guess):
      if ch == solution[i]:
        continue
      j = idx(ch)
      if cnt[j] > 0:
        cnt[j] -= 1
        pseudo += 1
    return hits, pseudo

Complexity

  • ⏰ Time complexity: O(L) where L is the length of the code (here L=4), because we scan the strings twice.
  • 🧺 Space complexity: O(1) — constant extra space for counts.

Method 2 — Bit-mask / small-alphabet trick

Intuition

For very small fixed alphabets (here 4 colors) you can pack presence information into small integers and test membership with bit operations; however frequency counts are clearer and safer when duplicates exist.

Approach

  • First pass: count hits and build a frequency mask/map for non-hit solution colors.
  • Second pass: for non-hits in guess, check membership in the frequency structure and update pseudo-hits accordingly.

Code (sketch)

Java (sketch)
1

// Similar to Method 1 but representing counts in small arrays/bitfields.

Complexity

  • ⏰ Time complexity: O(L).
  • 🧺 Space complexity: O(1).

Notes & References

  • Equivalent problem on LeetCode: “Bulls and Cows” (LC 299).
  • Original references and implementations are listed under source_links in frontmatter.