Skip to main content
Talentd

Bulls and Cows - Solution & Explanation

MediumHash TableStringCounting19 min readAsked at: Amazon, Meta, Google +4
Practice this problem

Problem Statement

You are playing the Bulls and Cows game with your friend.

You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:

  • The number of "bulls", which are digits in the guess that are in the correct position.
  • The number of "cows", which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.

Given the secret number secret and your friend's guess guess, return the hint for your friend's guess.

The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.

 

Example 1:

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

Example 2:

Input: secret = "1123", guess = "0111"
Output: "1A1B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1123"        "1123"
  |      or     |
"0111"        "0111"
Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.

 

Constraints:

  • 1 <= secret.length, guess.length <= 1000
  • secret.length == guess.length
  • secret and guess consist of digits only.

Approach Overview

Problem Overview: You receive two equal-length strings: secret and guess. A bull means the digit matches in both value and position. A cow means the digit exists in the secret but appears in a different position. The task is to compute counts for both and return them in the format xAyB.

Approach 1: Counting Bulls and Cows with Two Passes (O(n) time, O(1) space)

First iterate through both strings and count bulls directly by checking secret[i] == guess[i]. For digits that don't match, track their frequencies using two counting arrays of size 10 (since digits range from 0–9). After the first pass, run a second pass over the digit counts and sum the minimum frequency for each digit to compute cows. The key idea: unmatched digits from both strings contribute to cows if their counts overlap. This method avoids expensive searches and keeps memory constant. The approach relies on simple frequency counting, a common pattern in counting problems and string processing.

Approach 2: Single Pass Hashmap Tracking (O(n) time, O(1) space)

This version computes bulls and cows in a single traversal. Maintain a hash map (or array of size 10) that tracks the balance of digits seen in secret versus guess. When characters differ, increment the count for the secret digit and decrement for the guess digit. If a previously seen opposite imbalance exists (for example the guess digit appeared earlier in secret), that forms a cow. Each update checks whether the counter crosses zero to detect matches. The trick is that the map tracks surplus digits from both sides simultaneously, so cows are detected immediately without a second pass. This approach is compact and commonly used in interview solutions involving hash table frequency balancing.

Recommended for interviews: The single-pass hashmap approach is typically what interviewers expect because it shows you can track frequency differences while scanning once. The two-pass counting method is also acceptable and often easier to reason about during implementation. Mentioning both demonstrates strong problem-solving progression: brute logic first (count bulls, track digits), then optimization by merging the work into a single pass.

Approach 1: Counting Bulls and Cows with Two Passes

The idea is to first determine the number of bulls by comparing characters at the same position in both the secret and the guess. In the first pass over the strings, count all bulls and track unmatched characters using two separate frequency arrays. In the second pass, use the frequency arrays to compute the number of cows by checking the minimum frequency of each character in unmatched parts.

In this C solution, two integer arrays secretCount and guessCount are used to count how many times each digit appears in the unmatched parts of secret and guess. After counting bulls and populating these arrays in the first loop, the second loop calculates cows by summing the minimum of matched counts in secretCount and guessCount.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(1), where n is the length of the secret or guess.

Try this approach in the editor →

Approach 2: Single Pass Hashmap Tracking

Instead of performing two separate passes, this method uses a hashmap (or dictionary) to update the unmatched digits' count as it checks for bulls and non-bulls in a single iteration over the inputs. It utilizes incremental checking for cows during the mismatched segments.

This C function uses a single-pass approach with an array used as a hashmap to track digits. When encountering a mismatch, it checks and updates the hashmap to calculate cows immediately.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Counting

We create two counters, cnt1 and cnt2, to count the occurrence of each digit in the secret number and the friend's guess respectively. At the same time, we create a variable x to count the number of bulls.

Then we iterate through the secret number and the friend's guess. If the current digit is the same, we increment x by one. Otherwise, we increment the count of the current digit in the secret number and the friend's guess respectively.

Finally, we iterate through each digit in cnt1, take the minimum count of the current digit in cnt1 and cnt2, and add this minimum value to the variable y.

In the end, we return the values of x and y.

The time complexity is O(n), where n is the length of the secret number and the friend's guess. The space complexity is O(|\Sigma|), where |\Sigma| is the size of the character set. In this problem, the character set is digits, so |\Sigma| = 10.

Code

PythonJavaC++GoTypeScriptPHP

Python

Java

C++

Go

TypeScript

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Counting Bulls and Cows with Two Passes

Time Complexity: O(n), Space Complexity: O(1), where n is the length of the secret or guess.

Single Pass Hashmap Tracking

Time Complexity: O(n), Space Complexity: O(1).

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Pass CountingO(n)O(1)Best when clarity matters; easy to reason about using frequency arrays
Single Pass Hashmap TrackingO(n)O(1)Preferred in interviews; computes bulls and cows simultaneously in one traversal

Video Solution

bulls and cows | bulls and cows leetcode | leetcode 299 | string • Naresh Gupta • 16,096 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Bulls and Cows easy or hard?
The problem is rated Medium because the logic is simple but easy to implement incorrectly. Handling bulls separately from cows and avoiding double counting requires careful frequency tracking.
How to solve Bulls and Cows in O(n)?
Traverse both strings simultaneously. Count bulls when digits match at the same index. For mismatches, update a digit frequency map or array and detect cows when a previously seen opposite imbalance appears. This keeps the algorithm linear.
What is the best approach for Bulls and Cows?
The single-pass hashmap or counting-array approach is generally the best. It scans both strings once while tracking digit imbalances. Time complexity is O(n) with O(1) space because digits are limited to 0–9.
What data structure is used in Bulls and Cows?
Most implementations use a fixed-size counting array or a hash table to track digit frequency differences between the secret and guess strings. Since digits range from 0 to 9, an array of size 10 is usually sufficient.
What is the time complexity of Bulls and Cows?
Both common solutions run in O(n) time where n is the length of the strings. Each character is processed once or twice depending on the implementation, and the digit frequency array remains constant size.
Bulls and Cows Python or Java solution approach?
Python and Java implementations typically use an integer array of size 10 to track digit counts. During iteration, increments and decrements reveal when a digit forms a cow, while direct matches count as bulls.
Is Bulls and Cows asked at Google, Amazon, or Meta?
Bulls and Cows appears in interview prep lists for companies like Amazon and Google because it tests string traversal, frequency counting, and careful state tracking. Variants also appear in system and algorithm interview practice sets.

Ready to solve this problem?

Practice Bulls and Cows with our built-in code editor and test cases.

Practice on FleetCode
Previous

Make Number of Distinct Characters Equal