Bulls and Cows

Compute bulls (correct digit + position) and cows (correct digit, wrong position) for a guess.

Medium
Time O(N) Space O(1)
LeetCode
3 min read
hash-map counting

Problem#

Given a secret and a guess (same length, digits 0-9), return "<bulls>A<cows>B" where bulls are correct-digit-and-position matches and cows are digits in guess that exist in secret at a different position (and aren’t already counted as bulls).

Examples#

  • secret = "1807", guess = "7810""1A3B".
  • secret = "1123", guess = "0111""1A1B".

Constraints#

  • 1 <= secret.length, guess.length <= 1000, equal length, digits only.

Hints#

Hint
One pass: count bulls directly; for non-bull positions, tally digit frequencies in secret and guess and take the minimum per digit.

Approach#

Single pass. If secret[i] == guess[i], increment bulls. Otherwise increment the digit counts for both. Cows = sum over digits of min(secretCnt[d], guessCnt[d]).

Solution#

Bulls and Cows
class Solution {
public:
string getHint(string secret, string guess) {
int bulls = 0, cows = 0;
int s[10] = {0}, g[10] = {0};
for (int i = 0; i < (int)secret.size(); ++i) {
if (secret[i] == guess[i]) ++bulls;
else { ++s[secret[i] - '0']; ++g[guess[i] - '0']; }
}
for (int d = 0; d < 10; ++d) cows += min(s[d], g[d]);
return to_string(bulls) + "A" + to_string(cows) + "B";
}
};

Editorial#

Counting only the non-bull positions for cows is the key — it prevents double-counting a position as both bull and cow. min(secretCnt[d], guessCnt[d]) gives the maximum number of cow pairings per digit (each cow needs one occurrence on each side).

Complexity#

  • Time: O(N).
  • Space: O(1) — fixed int[10].

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.