Bulls and Cows solution and explanation
Google
9 more videos on this problem
bulls and cows | bulls and cows leetcode | leetcode 299 | stringNaresh Gupta · 9:56 · 16K views
Bulls and Cows | Leet code 299 | Theory explained + Python codeSai Anish Malla · 13:04 · 6K views
Bulls And Cows Leetcode | Leetcode 299 | Leetcode September ChallengeCode Bashers · 12:43 · 6K views
Leetcode - Bulls and Cows (Python)Timothy H Chang · 5:22 · 4K views
Bulls and Cows | Leetcode September Challenge Day10 Leetcode 299Coding Decoded · 7:06 · 2K views
299. Bulls and Cows | LEETCODE MEDIUMcode Explainer · 4:58 · 2K views
LeetCode 299: Bulls and Cows - Detailed Explanation and Solution (Python)Cameron Porteous · 11:33 · 1K views
LeetCode #299 Bulls and Cows - Solution in C++Programming Tutorials · 7:35 · 991 views
299. Bulls and Cows 🔥| Leetcode | Level 1 | JAVAProCode · 16:39 · 555 views
Daily Leetcode #163: Sep 10, 2020 - 299. Bulls and CowsProgramming Live with Larry · 6:20 · 356 views
The problem
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 <= 1000secret.length == guess.lengthsecretandguessconsist 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.
def getHint(secret: str, guess: str) -> str:
bulls = 0
cows = 0
secret_count = [0] * 10
guess_count = [0] * 10
for s, g in zip(secret, guess):
if s == g:
bulls += 1
else:
secret_count[int(s)] += 1
guess_count[int(g)] += 1
for sc, gc in zip(secret_count, guess_count):
cows += min(sc, gc)
return f"{bulls}A{cows}B"public class Solution {
public String getHint(String secret, String guess) {
int bulls = 0, cows = 0;
int[] secretCount = new int[10];
int[] guessCount = new int[10];
for (int i = 0; i < secret.length(); i++) {
if (secret.charAt(i) == guess.charAt(i)) {
bulls++;
} else {
secretCount[secret.charAt(i) - '0']++;
guessCount[guess.charAt(i) - '0']++;
}
}
for (int i = 0; i < 10; i++) {
cows += Math.min(secretCount[i], guessCount[i]);
}
return bulls + "A" + cows + "B";
}
}#include <iostream>
#include <vector>
#include <string>
#include <sstream>
std::string getHint(std::string secret, std::string guess) {
int bulls = 0, cows = 0;
std::vector<int> secretCount(10, 0), guessCount(10, 0);
for (size_t i = 0; i < secret.size(); i++) {
if (secret[i] == guess[i]) {
bulls++;
} else {
secretCount[secret[i] - '0']++;
guessCount[guess[i] - '0']++;
}
}
for (int i = 0; i < 10; i++) {
cows += std::min(secretCount[i], guessCount[i]);
}
std::ostringstream oss;
oss << bulls << "A" << cows << "B";
return oss.str();
}function getHint(secret, guess) {
let bulls = 0;
let cows = 0;
const secretCount = new Array(10).fill(0);
const guessCount = new Array(10).fill(0);
for (let i = 0; i < secret.length; i++) {
if (secret[i] === guess[i]) {
bulls++;
} else {
secretCount[secret[i]]++;
guessCount[guess[i]]++;
}
}
for (let i = 0; i < 10; i++) {
cows += Math.min(secretCount[i], guessCount[i]);
}
return `${bulls}A${cows}B`;
}#include <stdio.h>
#include <string.h>
char* getHint(char* secret, char* guess) {
static char hint[10];
int bulls = 0, cows = 0;
int secretCount[10] = {0}, guessCount[10] = {0};
int length = strlen(secret);
for (int i = 0; i < length; i++) {
if (secret[i] == guess[i]) {
bulls++;
} else {
secretCount[secret[i] - '0']++;
guessCount[guess[i] - '0']++;
}
}
for (int i = 0; i < 10; i++) {
cows += secretCount[i] < guessCount[i] ? secretCount[i] : guessCount[i];
}
sprintf(hint, "%dA%dB", bulls, cows);
return hint;
}public class Solution {
public string GetHint(string secret, string guess) {
int bulls = 0, cows = 0;
int[] secretCount = new int[10];
int[] guessCount = new int[10];
for (int i = 0; i < secret.Length; i++) {
if (secret[i] == guess[i]) {
bulls++;
} else {
secretCount[secret[i] - '0']++;
guessCount[guess[i] - '0']++;
}
}
for (int i = 0; i < 10; i++) {
cows += Math.Min(secretCount[i], guessCount[i]);
}
return bulls + "A" + cows + "B";
}
}In the Python solution, the zip function efficiently pairs characters from secret and guess for comparison. A second loop then determines the number of potential cow matches.
Time Complexity: O(n), Space Complexity: O(1).
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.
def getHint(secret: str, guess: str) -> str:
bulls = 0
cows = 0
map = [0] * 10
for i in range(len(secret)):
if secret[i] == guess[i]:
bulls += 1
else:
if map[int(secret[i])] < 0:
cows += 1
if map[int(guess[i])] > 0:
cows += 1
map[int(secret[i])] += 1
map[int(guess[i])] -= 1
return f"{bulls}A{cows}B"import java.util.*;
public class Solution {
public String getHint(String secret, String guess) {
int bulls = 0, cows = 0;
int[] map = new int[10];
for (int i = 0; i < secret.length(); i++) {
if (secret.charAt(i) == guess.charAt(i)) {
bulls++;
} else {
if (map[secret.charAt(i) - '0'] < 0) cows++;
if (map[guess.charAt(i) - '0'] > 0) cows++;
map[secret.charAt(i) - '0']++;
map[guess.charAt(i) - '0']--;
}
}
return bulls + "A" + cows + "B";
}
}#include <iostream>
#include <unordered_map>
#include <string>
#include <sstream>
std::string getHint(std::string secret, std::string guess) {
int bulls = 0, cows = 0;
std::unordered_map<char, int> map;
for (size_t i = 0; i < secret.length(); i++) {
if (secret[i] == guess[i]) {
bulls++;
} else {
if (map[secret[i]] < 0) cows++;
if (map[guess[i]] > 0) cows++;
map[secret[i]]++;
map[guess[i]]--;
}
}
return std::to_string(bulls) + "A" + std::to_string(cows) + "B";
}function getHint(secret, guess) {
let bulls = 0;
let cows = 0;
const map = new Array(10).fill(0);
for (let i = 0; i < secret.length; i++) {
if (secret[i] === guess[i]) {
bulls++;
} else {
if (map[secret[i]] < 0) cows++;
if (map[guess[i]] > 0) cows++;
map[secret[i]]++;
map[guess[i]]--;
}
}
return `${bulls}A${cows}B`;
}#include <stdio.h>
#include <string.h>
char* getHint(char* secret, char* guess) {
static char hint[10];
int bulls = 0, cows = 0;
int map[10] = {0};
for (int i = 0; i < strlen(secret); i++) {
int s = secret[i] - '0';
int g = guess[i] - '0';
if (s == g) {
bulls++;
} else {
if (map[s] < 0) cows++;
if (map[g] > 0) cows++;
map[s]++;
map[g]--;
}
}
sprintf(hint, "%dA%dB", bulls, cows);
return hint;
}public class Solution {
public string GetHint(string secret, string guess) {
int bulls = 0, cows = 0;
int[] map = new int[10];
for (int i = 0; i < secret.Length; i++) {
if (secret[i] == guess[i]) {
bulls++;
} else {
if (map[secret[i] - '0'] < 0) cows++;
if (map[guess[i] - '0'] > 0) cows++;
map[secret[i] - '0']++;
map[guess[i] - '0']--;
}
}
return bulls + "A" + cows + "B";
}
}Python's solution utilizes a list like a hashmap to handle digit tracking. Each character is evaluated for its matching status, allowing cow counting and updating mappings in one pass.
Time Complexity: O(n), Space Complexity: O(1).
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.
function getHint(secret: string, guess: string): string {
const cnt1: number[] = Array(10).fill(0);
const cnt2: number[] = Array(10).fill(0);
let x: number = 0;
for (let i = 0; i < secret.length; ++i) {
if (secret[i] === guess[i]) {
++x;
} else {
++cnt1[+secret[i]];
++cnt2[+guess[i]];
}
}
let y: number = 0;
for (let i = 0; i < 10; ++i) {
y += Math.min(cnt1[i], cnt2[i]);
}
return `${x}A${y}B`;
}func getHint(secret string, guess string) string {
x, y := 0, 0
cnt1 := [10]int{}
cnt2 := [10]int{}
for i, c := range secret {
a, b := int(c-'0'), int(guess[i]-'0')
if a == b {
x++
} else {
cnt1[a]++
cnt2[b]++
}
}
for i, c := range cnt1 {
y += min(c, cnt2[i])
}
return fmt.Sprintf("%dA%dB", x, y)
}class Solution {
/**
* @param String $secret
* @param String $guess
* @return String
*/
function getHint($secret, $guess) {
$cnt1 = array_fill(0, 10, 0);
$cnt2 = array_fill(0, 10, 0);
$x = 0;
for ($i = 0; $i < strlen($secret); ++$i) {
if ($secret[$i] === $guess[$i]) {
++$x;
} else {
++$cnt1[(int) $secret[$i]];
++$cnt2[(int) $guess[$i]];
}
}
$y = 0;
for ($i = 0; $i < 10; ++$i) {
$y += min($cnt1[$i], $cnt2[$i]);
}
return "{$x}A{$y}B";
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Counting Bulls and Cows with Two Passes | Time Complexity: O(n), Space Complexity: O(1). |
| Single Pass Hashmap Tracking | Time Complexity: O(n), Space Complexity: O(1). |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pass Counting | O(n) | O(1) | Best when clarity matters; easy to reason about using frequency arrays |
| Single Pass Hashmap Tracking | O(n) | O(1) | Preferred in interviews; computes bulls and cows simultaneously in one traversal |
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.