299. Bulls and Cows

299

MediumArrays and HashingHash / digit countingPosition match plus digit-frequency overlap

Bulls and Cows

You are playing Bulls and Cows. Given the secret number and the friend's guess as equal-length digit strings, return the hint as "xAyB": x bulls are digits correct in both value and position, and y cows are digits present in the secret but placed at a wrong position.

Open official problem prompt ↗

In plain English

Produce the bulls-and-cows hint counting exact matches and misplaced-but-present digits.

Picture it like this

Like grading a lock-combination guess: dials that are exactly right are bulls, and dials whose number appears somewhere else on the real combination but in the wrong slot are cows.

Example

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Why: The 8 at index 1 is a bull; the digits 1, 0, and 7 exist in the secret but at different positions, giving 3 cows.

Constraints

1 <= secret.length, guess.length <= 1000secret.length == guess.lengthsecret and guess consist of digits onlyguess and secret may contain duplicate digits

Pattern lesson

See the pattern, then code

Position match plus digit-frequency overlap

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. Bulls are found by direct position comparison; for the remaining non-bull positions, the number of cows for each digit is the minimum of how many times it is left over in the secret and in the guess.

New words, made simpleKnow these before the algorithm

Bull: A digit that matches both value and position between guess and secret.
Cow: A digit present in the secret but placed at the wrong position in the guess.
Leftover count: The frequency of each digit among positions that were not bulls.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Mark and rescan

The nested search over the secret is quadratic and error-prone.

First pass marks bulls, second pass searches the secret for each guess digit and mutates matched slots.

Time O(n^2)Space O(n)

Best choiceBulls then frequency overlap

Single pass plus a fixed 10-slot tally is optimal.

Count bulls in one pass; for non-bulls, tally digit frequencies and sum the per-digit minimum for cows.

Time O(n)Space O(1)

The rule we keep true

Invariant

A digit counted as a bull is never added to either leftover tally, so bulls and cows never double-count the same position.

Why this is correct

Reasoning

For a fixed digit d, the number of cows it can contribute is limited by how many unmatched copies exist on each side, which is min(secretLeftover[d], guessLeftover[d]). Because bull positions are excluded from both tallies, summing these minima over all ten digits yields exactly the cows without overlap.

The algorithm in three movesSay these aloud before coding

1Walk both strings together, counting a bull whenever the digits match at the same position

bull at idx1 (8=8)

2For non-matching positions, tally leftover digit frequencies separately for secret and guess

secretLeft:{1,0,7} guessLeft:{7,1,0}

3For each digit 0-9, add min(secretLeftover, guessLeftover) to the cow count

cows = 3 -> 1A3B

4Format the result as bulls A cows B

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Reads=1, g=7

2 · AskDo they match?

3 · Update statebulls=0

4 · ResultMismatch: secretLeft[1]++, guessLeft[7]++.

Key takeaway

Only index 1 aligns as a bull; the other three digits overlap out of place as cows.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-11Single pass split
Matching positions increment bulls; mismatched positions feed the two digit-frequency arrays for later cow computation.
2
Lines 12Overlap for cows
Summing min(secret_count[d], guess_count[d]) counts each digit only as many times as it can be reused out of place.
3
Lines 13Format
Assembles the required xAyB string.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

All bulls, e.g. secret == guess, gives nA0B
No matches at all gives 0A0B when digit sets are disjoint
Repeated digits like secret="1123", guess="0111" where cows are capped by the smaller side's count
Length one strings

Common beginner mistakes

Counting a digit as both a bull and a cow by tallying it before checking the position match
Summing total frequencies instead of the per-digit minimum, which overcounts cows when duplicate counts differ
Iterating with two nested loops over the strings and mutating during iteration

Check your understanding

Why do we take the minimum of the two leftover counts for each digit rather than either one alone?

Bulls and Cows

Bulls and Cows

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing