Bulls and Cows
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses two passes over the input strings. The first pass identifies and counts "bulls" (digits in the correct position). The second pass uses nested loops to find "cows" (correct digits in the wrong position) among the remaining characters. To avoid recounting, boolean flags are used to mark characters that have been matched as either a bull or a cow.
Algorithm
- Initialize
bullsandcowsto 0. - Get the length
nof the strings. - Create two boolean arrays,
secretUsedandguessUsed, of sizen, initialized tofalse. - First Pass (Bulls): Iterate from
i = 0ton-1. Ifsecret.charAt(i)equalsguess.charAt(i), incrementbullsand setsecretUsed[i]andguessUsed[i]totrue. - Second Pass (Cows): Iterate through the
guessstring with indexi. IfguessUsed[i]isfalse, start an inner loop through thesecretstring with indexj. - In the inner loop, if
secretUsed[j]isfalseandguess.charAt(i)equalssecret.charAt(j), we've found a cow. Incrementcows, setsecretUsed[j]totrue, and break the inner loop to prevent matching the samesecretcharacter again. - Finally, format the result as a string:
bulls + "A" + cows + "B".
Walkthrough
This method directly simulates the matching process. It first iterates through the strings to find all exact matches (bulls) and marks them as used. Then, it performs a second, nested iteration on the remaining, unused characters to find matches in wrong positions (cows). This ensures that a character is not counted as both a bull and a cow, and also that each character is used in at most one match.
class Solution { public String getHint(String secret, String guess) { int bulls = 0; int cows = 0; int n = secret.length(); boolean[] secretUsed = new boolean[n]; boolean[] guessUsed = new boolean[n]; // First pass for bulls for (int i = 0; i < n; i++) { if (secret.charAt(i) == guess.charAt(i)) { bulls++; secretUsed[i] = true; guessUsed[i] = true; } } // Second pass for cows for (int i = 0; i < n; i++) { if (guessUsed[i]) { continue; } for (int j = 0; j < n; j++) { if (!secretUsed[j] && secret.charAt(j) == guess.charAt(i)) { cows++; secretUsed[j] = true; break; // Found a match for guess[i], move to the next guess character } } } return bulls + "A" + cows + "B"; }}Complexity
Time
O(n^2), where `n` is the length of the strings. The first pass is `O(n)`, but the second pass involves nested loops, leading to `O(n^2)` in the worst case.
Space
O(n), where `n` is the length of the strings. This is required to store the `secretUsed` and `guessUsed` boolean arrays.
Trade-offs
Pros
Simple to understand and implement.
The logic directly follows the problem definition.
Cons
Inefficient due to the
O(n^2)time complexity, which can be slow for larger inputs.Uses extra space proportional to the input size.
This approach improves upon the brute-force method by using frequency maps (or arrays) to count characters, avoiding the nested loop for finding cows. It still uses two passes: the first pass identifies bulls and simultaneously builds frequency counts for the non-bull characters. The second pass calculates the number of cows by comparing the frequency counts.
Algorithm
- Initialize
bullsandcowsto 0. - Create two integer arrays,
secretCountsandguessCounts, of size 10 (for digits 0-9), initialized to 0. - First Pass (Bulls and Frequencies): Iterate from
i = 0ton-1. - If
secret.charAt(i)equalsguess.charAt(i), incrementbulls. - Otherwise, increment the count for
secret.charAt(i)insecretCountsand forguess.charAt(i)inguessCounts. - Second Pass (Cows): Iterate from
d = 0to 9. For each digit, the number of cows is the minimum of its count insecretCountsandguessCounts. Add this minimum value to the totalcows. - Finally, format the result as a string:
bulls + "A" + cows + "B".
Walkthrough
The key idea is to separate the bull-finding logic from the cow-finding logic. After the first pass identifies all bulls, we are left with two sets of characters (from secret and guess) that are at incorrect positions. The number of cows is simply the number of characters common to both these sets. We can find this by counting the frequencies of each digit in both sets and then for each digit, taking the minimum of the two counts. This avoids the expensive O(n^2) search for cows.
class Solution { public String getHint(String secret, String guess) { int bulls = 0; int cows = 0; int[] secretCounts = new int[10]; int[] guessCounts = new int[10]; // First pass for bulls and counting non-bull characters for (int i = 0; i < secret.length(); i++) { char s = secret.charAt(i); char g = guess.charAt(i); if (s == g) { bulls++; } else { secretCounts[s - '0']++; guessCounts[g - '0']++; } } // Second pass for cows for (int i = 0; i < 10; i++) { cows += Math.min(secretCounts[i], guessCounts[i]); } return bulls + "A" + cows + "B"; }}Complexity
Time
O(n), where `n` is the length of the strings. The first pass takes `O(n)` and the second pass takes `O(1)` (since it iterates 10 times).
Space
O(1), as the frequency arrays have a constant size (10), independent of the input string length.
Trade-offs
Pros
Much more efficient than the brute-force approach with linear time complexity.
Uses constant extra space, as the size of the frequency arrays does not depend on the input size.
Cons
Requires two separate passes over the data, which is slightly less efficient than a single-pass solution.
This is the most optimal approach, solving the problem in a single pass. It calculates bulls and cows simultaneously. A single frequency array is used to keep track of the balance of non-bull digits between the secret and guess strings. A positive count for a digit indicates a surplus in secret, while a negative count indicates a surplus in guess.
Algorithm
- Initialize
bullsandcowsto 0. - Create a single integer array
countsof size 10, initialized to 0. - Single Pass: Iterate from
i = 0ton-1. - Let
sbe the digit fromsecretandgbe the digit fromguessat indexi. - If
s == g, incrementbulls. - If
s != g:- Check
counts[g]. If it's positive, it means we've previously seen this digit insecret(as a non-bull) that can now be matched with the currentg. So, we've found a cow. Incrementcows. - Check
counts[s]. If it's negative, it means we've previously seen this digit inguess(as a non-bull) that can now be matched with the currents. So, we've found a cow. Incrementcows. - Update the balance: increment
counts[s](we've seen one mores) and decrementcounts[g](we've seen one moreg).
- Check
- Finally, format the result as a string:
bulls + "A" + cows + "B".
Walkthrough
This elegant solution processes both strings in a single loop. For each position, it first checks for a bull. If it's not a bull, it uses a single array to track the counts of mismatched digits. A positive value counts[d] means secret has seen d more times than guess among mismatched characters, while a negative value means the opposite. A cow is found whenever we process a digit that can cancel out a previously recorded surplus from the other string. For example, if we process guess.charAt(i) = d and counts[d] is positive, it means there's an unmatched d from secret available, forming a cow. Similarly, if we process secret.charAt(i) = d and counts[d] is negative, there's an unmatched d from guess available.
class Solution { public String getHint(String secret, String guess) { int bulls = 0; int cows = 0; int[] counts = new int[10]; for (int i = 0; i < secret.length(); i++) { int s = secret.charAt(i) - '0'; int g = guess.charAt(i) - '0'; if (s == g) { bulls++; } else { // If guess digit g was seen in secret before (secret has a surplus) if (counts[g] > 0) { cows++; } // If secret digit s was seen in guess before (guess has a surplus) if (counts[s] < 0) { cows++; } // Update balances counts[s]++; counts[g]--; } } return bulls + "A" + cows + "B"; }}Complexity
Time
O(n), where `n` is the length of the strings, as we iterate through the strings only once.
Space
O(1), as the frequency array has a constant size (10).
Trade-offs
Pros
Most efficient solution with
O(n)time andO(1)space.Processes the input in a single pass, which can be faster in practice due to better cache performance.
It's a clever and compact way to solve the problem.
Cons
The logic for updating cows and the frequency array can be slightly less intuitive to grasp at first compared to the two-pass approach.
Solutions
Solution
class Solution { public String getHint ( String secret , String guess ) { int x = 0 , y = 0 ; int [] cnt1 = new int [ 10 ]; int [] cnt2 = new int [ 10 ]; for ( int i = 0 ; i < secret . length (); ++ i ) { int a = secret . charAt ( i ) - '0' , b = guess . charAt ( i ) - '0' ; if ( a == b ) { ++ x ; } else { ++ cnt1 [ a ]; ++ cnt2 [ b ]; } } for ( int i = 0 ; i < 10 ; ++ i ) { y += Math . min ( cnt1 [ i ], cnt2 [ i ]); } return String . format ( "%dA%dB" , x , y ); } }class Solution { public: string getHint ( string secret , string guess ) { int x = 0 , y = 0 ; vector < int > cnt1 ( 10 ); vector < int > cnt2 ( 10 ); for ( int i = 0 ; i < secret . size (); ++ i ) { int a = secret [ i ] - '0' , b = guess [ i ] - '0' ; if ( a == b ) ++ x ; else { ++ cnt1 [ a ]; ++ cnt2 [ b ]; } } for ( int i = 0 ; i < 10 ; ++ i ) y += min ( cnt1 [ i ], cnt2 [ i ]); return to_string ( x ) + "A" + to_string ( y ) + "B" ; } };class Solution : def getHint ( self , secret : str , guess : str ) -> str : x = y = 0 cnt1 = [ 0 ] * 10 cnt2 = [ 0 ] * 10 for i in range ( len ( secret )): if secret [ i ] == guess [ i ]: x += 1 else : cnt1 [ int ( secret [ i ])] += 1 cnt2 [ int ( guess [ i ])] += 1 for i in range ( 10 ): y += min ( cnt1 [ i ], cnt2 [ i ]) return f ' { x } A { y } B'Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.