Bulls and Cows
Compute bulls (correct digit + position) and cows (correct digit, wrong position) for a guess.
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#
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"; }};func getHint(secret string, guess string) string { bulls, cows := 0, 0 var s, g [10]int for i := 0; i < len(secret); i++ { if secret[i] == guess[i] { bulls++ } else { s[secret[i]-'0']++ g[guess[i]-'0']++ } } for d := 0; d < 10; d++ { if s[d] < g[d] { cows += s[d] } else { cows += g[d] } } return fmt.Sprintf("%dA%dB", bulls, cows)}class Solution: def getHint(self, secret: str, guess: str) -> str: bulls = cows = 0 s = [0] * 10 g = [0] * 10 for a, b in zip(secret, guess): if a == b: bulls += 1 else: s[int(a)] += 1 g[int(b)] += 1 for d in range(10): cows += min(s[d], g[d]) return f"{bulls}A{cows}B"var getHint = function(secret, guess) { let bulls = 0, cows = 0; const s = new Array(10).fill(0); const g = new Array(10).fill(0); for (let i = 0; i < secret.length; i++) { if (secret[i] === guess[i]) { bulls++; } else { s[secret.charCodeAt(i) - 48]++; g[guess.charCodeAt(i) - 48]++; } } for (let d = 0; d < 10; d++) cows += Math.min(s[d], g[d]); return `${bulls}A${cows}B`;};class Solution { public String getHint(String secret, String guess) { int bulls = 0, cows = 0; int[] s = new int[10]; int[] g = new int[10]; for (int i = 0; i < secret.length(); i++) { char a = secret.charAt(i), b = guess.charAt(i); if (a == b) { bulls++; } else { s[a - '0']++; g[b - '0']++; } } for (int d = 0; d < 10; d++) cows += Math.min(s[d], g[d]); return bulls + "A" + cows + "B"; }}function getHint(secret: string, guess: string): string { let bulls = 0, cows = 0; const s: number[] = new Array(10).fill(0); const g: number[] = new Array(10).fill(0); for (let i = 0; i < secret.length; i++) { if (secret[i] === guess[i]) { bulls++; } else { s[secret.charCodeAt(i) - 48]++; g[guess.charCodeAt(i) - 48]++; } } for (let d = 0; d < 10; d++) cows += Math.min(s[d], g[d]); return `${bulls}A${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#
Related#