299. Bulls and Cows
Model: qwen3.5:9b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 44.7%
Problem Breakdown
We are given two strings of equal length containing digits: secret (the hidden number) and guess. We need to return a formatted string "xAyB", where x is the count of “bulls” and y is the count of “cows”.
- Bull (
A): A digit inguessthat matches the corresponding digit insecretat the same index. - Cow (
B): A digit inguessthat exists insecretbut not at the correct position (wrong index). Crucially, this is a non-bull match where digits can be rearranged to become bulls.
Key Constraints & Tricky Parts:
- Duplicates: The problem explicitly states duplicates are allowed and must be handled correctly. A digit in
secretcannot contribute to both a Bull and a Cow simultaneously if it’s the same instance, but multiple instances of the same digit can exist (e.g., two ‘1’s). We need to ensure we don’t double-count matches for digits that appear more than once. - Format: The output must be strictly
"xAyB".
Intuition
A brute-force approach would involve checking every position in guess against secret, but determining the number of cows is tricky because a digit might match multiple times or not at all depending on how many instances exist. Checking permutations to find valid cow positions leads to exponential complexity, which we want to avoid.
The core insight relies on frequency counting (Hash Table/Array).
- Bulls are easy: Iterate through indices and count exact matches (
secret[i] == guess[i]). These specific digits should be “consumed” so they don’t contribute to the cow count later. - Cows: For any digit
d, if it appears in both strings, we can match at most as many times as the minimum frequency of that digit exists between them (excluding bulls). - However, a simpler mathematical relationship works: The total number of matching digits possible regardless of position is determined by summing
min(count_secret[d], count_guess[d])for all digitsd. Since Bulls are exact matches included in this calculation, we can simply subtract the actual Bull count from this Total Potential Matches to get Cows.- Wait, let’s refine that logic: If I calculate total potential matches based on frequency (ignoring position), every bull is inherently a match counted there. Every cow is also a match counted there but not at the correct index. So
Cows = sum(min(frequencies)) - Bulls. This avoids complex state management during iteration and simplifies to two passes: one for counting frequencies, one for finding bulls (or vice versa).
- Wait, let’s refine that logic: If I calculate total potential matches based on frequency (ignoring position), every bull is inherently a match counted there. Every cow is also a match counted there but not at the correct index. So
Approach
- Initialize Counters: Create frequency arrays of size 10 (for digits ‘0’-‘9’) for both
secretandguess. This is O(1) space since the alphabet is fixed. - Count Frequencies: Iterate through both strings once to populate these counters.
- Identify Bulls & Adjust Counts: Iterate through indices again (or just iterate one string). If characters match, increment a
bullscounter and decrement the frequency count for that digit in both maps?- Actually, using the formula derived in Intuition (
Cows = sum(min) - bulls) is cleaner. However, to be precise about “consumed” digits: - Better Implementation Strategy: Iterate through indices . If
secret[i] == guess[i], incrementbulls. Else if we can match the digit (checking remaining counts), it’s a cow? No, that requires complex logic. - Optimal Algorithm:
- Count frequencies of all digits in both strings into two arrays/maps (
countSandcountG). - Iterate through indices . If
secret[i] == guess[i], incrementbulls. Decrement the count for that digit in both maps immediately? No, if we decrement on mismatch too it gets messy. - Correct Logic: Count frequencies first (ignoring position). Then iterate to find Bulls and subtract them from total potential matches calculated by frequency sums.
Wait, simply:
cows = sum(min(countS[d], countG[d])) - bulls. This works perfectly because every Bull is a valid match in the frequency domain that we must exclude from Cows.
- Count frequencies of all digits in both strings into two arrays/maps (
- Construct Output: Format string as
"xAyB".
- Actually, using the formula derived in Intuition (
Complexity Analysis
- Time Complexity: , where is the length of
secret(orguess). We iterate through both strings once to build frequency maps and potentially a second time or constant 10 iterations for summing. Since digits are fixed ‘0’-‘9’, map operations are O(1). - Space Complexity: . The space used is proportional to the number of unique characters (digits), which is bounded by 10, regardless of input size.
Solution
from typing import List
def getHint(secret: str, guess: str) -> str:
# Frequency arrays for digits '0'-'9'.
# Using lists instead of dicts for slightly better performance given fixed domain.
countS = [0] * 10
countG = [0] * 10
n = len(secret)
# Pass 1: Count frequencies in both strings
for i in range(n):
digit_s = int(secret[i])
digit_g = int(guess[i])
countS[digit_s] += 1
countG[digit_g] += 1
bulls = 0
# Pass 2: Count Bulls and calculate Cows based on frequency logic
for i in range(n):
if secret[i] == guess[i]:
bulls += 1
# Calculate total potential matches (Bulls + Cows) using min frequencies
cows = 0
for d in range(10):
common_matches = min(countS[d], countG[d])
cows += common_matches
# Subtract Bulls from Total Matches to get pure Cow count
cows -= bulls
return f"{bulls}A{cows}B"
# Example usage:
# print(getHint("1807", "7810")) -> Output: "1A3B"
Edge Cases Handled
- No Matches: If
secretandguessshare no digits, frequency counts will be disjoint or zero. Sum of mins is 0, Bulls=0, Cows=0. Correctly returns"0A0B". - All Digits Match (Permutation): E.g., S=“123”, G=“321”. Frequencies match exactly.
sum(min)= length(N). Bulls will be 0 (assuming no fixed points). Cows = N - 0 = N. Correctly returns"0ANB". - Duplicate Digits: E.g., S=“11”, G=“12”.
- FreqS: {1:2}, FreqG: {1:1, 2:1}. Min sum for ‘1’ is 1. Bulls=0 (indices don’t match). Cows = 1 - 0 = 1? Wait. S=“11”, G=“12”. Index 0 matches (‘1’). Bull=1. FreqS={1:2}, FreqG={1:1, 2:1}. Min sum for ‘1’ is min(2,1)=1. Total Matches = 1. Cows = 1 - 1 (Bull) = 0? Wait.
- Let’s re-verify S=“11”, G=“12”.
- Index 0: ‘1’==‘1’. Bull=1.
- FreqS={1:2}, FreqG={1:1, 2:1}. Min sum = min(2,1) for digit 1 + others (min is 0). Total Matches = 1.
- Cows = 1 - 1 = 0. Correct? S=“11”, G=“12”. One ‘1’ matches at pos 0. The other ‘1’ in secret has no match in guess (guess only has one ‘1’). So yes, 0 cows is correct.
- Example: S=“1807”, G=“7810” -> Bulls=1 (‘8’), Cows=3.
- FreqS={1:1,8:1,0:1,7:1}, FreqG={7:1,8:1,1:1,0:1}. Min sum = 4 (all digits match once). Bulls=1. Cows=3. Correct.
- Single Character: Handled by loop ranges correctly returning “0A0B” or “1A0B”.