Bulls and Cows
Medium · Arrays & Hashing · Explanation and code example
Exact Matches and Remaining Digit Counts
How it works
First count digits that match at the same position as bulls. For the remaining positions, build one frequency table per string. The minimum of the two counts for each digit gives cows without reusing digits that already counted as bulls.
Steps
- Count equal-position bulls.
- Count unmatched digits in two ten-element tables.
- Sum per-digit minima and format the bulls and cows counts.
Complexity
- Time: O(n).
- Space: O(1), because there are ten digit values.
Things to watch for
- Remove bulls before counting cows.
- Repeated digits are limited by the smaller remaining frequency.
- Format the result as xAyB.
Python code example
class Solution:
def getHint(self, secret: str, guess: str) -> str:
bulls = 0
secret_count, guess_count = [0] * 10, [0] * 10
for a, b in zip(secret, guess):
if a == b:
bulls += 1
else:
secret_count[int(a)] += 1
guess_count[int(b)] += 1
cows = sum(min(a, b) for a, b in zip(secret_count, guess_count))
return f"{bulls}A{cows}B"
C++ code example
class Solution {
public:
string getHint(string secret, string guess) {
int A = 0;
int B = 0;
vector<int> count1(10);
vector<int> count2(10);
for (int i = 0; i < secret.length(); ++i)
if (secret[i] == guess[i])
++A;
else {
++count1[secret[i] - '0'];
++count2[guess[i] - '0'];
}
for (int i = 0; i < 10; ++i)
B += min(count1[i], count2[i]);
return to_string(A) + "A" + to_string(B) + "B";
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.