Description
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.
Examples:
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.Solution in Python
To solve the “Bulls and Cows” game problem in Python, we can break down the problem into two main tasks:
- Counting Bulls: A “bull” is a digit in the guess that is both in the correct position and matches the corresponding digit in the secret number.
- Counting Cows: A “cow” is a digit in the guess that exists in the secret number but is in the wrong position.
Approach:
- First, traverse through both
secretandguessto count the number of bulls (i.e., when both the digit and its position match). - Then, for the remaining digits (those that are not bulls), count how many times they occur in both
secretandguess. The minimum of these counts will give the number of cows.
Steps:
- Initialize Counters:
- A counter for bulls.
- Two additional lists (or dictionaries) to keep track of non-bull digits in both
secretandguess.
- First Pass (Bulls):
- For each position in
secretandguess, if the digits match, increment the bull counter. - If the digits do not match, store the unmatched digits separately for both
secretandguess.
- For each position in
- Second Pass (Cows):
- For the remaining unmatched digits, compare their occurrences in
secretandguess. The number of cows for each digit is the minimum of its occurrence insecretandguess.
- For the remaining unmatched digits, compare their occurrences in
- Return the Result: Format the result as
"xAyB", wherexis the number of bulls andyis the number of cows.
Python
class Solution:
def getHint(self, secret: str, guess: str) -> str:
# Initialize bulls and cows counters
bulls = 0
# Dictionaries to track the frequency of unmatched digits in both secret and guess
secret_counts = {}
guess_counts = {}
# First pass: count bulls and record non-bull characters
for i in range(len(secret)):
if secret[i] == guess[i]:
# If the digits match in the same position, it's a bull
bulls += 1
else:
# If not a bull, record the unmatched digits
secret_counts[secret[i]] = secret_counts.get(secret[i], 0) + 1
guess_counts[guess[i]] = guess_counts.get(guess[i], 0) + 1
# Second pass: count cows
cows = 0
for digit in guess_counts:
if digit in secret_counts:
# Cows are the minimum of the unmatched digits in both secret and guess
cows += min(secret_counts[digit], guess_counts[digit])
# Return the result in "xAyB" format
return f"{bulls}A{cows}B"Explanation:
- Initialization:
bullsis initialized to 0 to count how many digits are bulls.- Two dictionaries
secret_countsandguess_countsare used to track the occurrences of unmatched digits insecretandguess, respectively.
- First Pass (Bulls Detection):
- We loop through the digits of
secretandguess. If the digits match at the same position, we increment thebullscounter. - If they do not match, the digits are stored in
secret_countsandguess_countsfor further cow calculations.
- We loop through the digits of
- Second Pass (Cows Calculation):
- For each digit that was unmatched in
guess, check if it exists insecret_counts. - The number of cows for each unmatched digit is the minimum between how many times that digit appears in
secretand inguess.
- For each digit that was unmatched in
- Final Result:
- The result is formatted as
"xAyB", wherexis the number of bulls andyis the number of cows.
- The result is formatted as
Solution in C++
C++
class Solution {
public:
string getHint(string secret, string guess) {
int bulls = 0; // To count bulls
int cows = 0; // To count cows
// Arrays to store the frequency of unmatched digits
int secret_counts[10] = {0}; // Frequency of digits in secret that are not bulls
int guess_counts[10] = {0}; // Frequency of digits in guess that are not bulls
// First pass: Count bulls and record non-bull digits
for (int i = 0; i < secret.size(); ++i) {
if (secret[i] == guess[i]) {
// If the digit matches in the same position, it's a bull
bulls++;
} else {
// If not a bull, increment the count for the digit in secret and guess
secret_counts[secret[i] - '0']++;
guess_counts[guess[i] - '0']++;
}
}
// Second pass: Count cows
for (int i = 0; i < 10; ++i) {
// For each digit, the number of cows is the minimum of unmatched counts
cows += std::min(secret_counts[i], guess_counts[i]);
}
// Return the result in "xAyB" format
return std::to_string(bulls) + "A" + std::to_string(cows) + "B";
}
};Solution in Javascript
JavaScript
var getHint = function(secret, guess) {
// Initialize counters for bulls and cows
let bulls = 0;
let cows = 0;
// Arrays to store the frequency of unmatched digits
let secretCounts = new Array(10).fill(0); // Frequency of digits in secret
let guessCounts = new Array(10).fill(0); // Frequency of digits in guess
// First pass: Count bulls and record unmatched digits
for (let i = 0; i < secret.length; i++) {
if (secret[i] === guess[i]) {
// If digits match at the same position, it's a bull
bulls++;
} else {
// Otherwise, count the digits in both secret and guess
secretCounts[secret[i]]++;
guessCounts[guess[i]]++;
}
}
// Second pass: Count cows
for (let i = 0; i < 10; i++) {
// Cows are the minimum of the unmatched digit counts in secret and guess
cows += Math.min(secretCounts[i], guessCounts[i]);
}
// Return the result in the format "xAyB"
return `${bulls}A${cows}B`;
};Solution in Java
Java
class Solution {
public String getHint(String secret, String guess) {
int bulls = 0; // To count bulls
int cows = 0; // To count cows
// Arrays to store the frequency of unmatched digits (size 10 for digits 0-9)
int[] secretCounts = new int[10]; // Frequency of digits in secret that are not bulls
int[] guessCounts = new int[10]; // Frequency of digits in guess that are not bulls
// First pass: Count bulls and record unmatched digits
for (int i = 0; i < secret.length(); i++) {
if (secret.charAt(i) == guess.charAt(i)) {
// If the digits match at the same position, it's a bull
bulls++;
} else {
// Otherwise, count unmatched digits in secret and guess
secretCounts[secret.charAt(i) - '0']++;
guessCounts[guess.charAt(i) - '0']++;
}
}
// Second pass: Count cows by comparing unmatched digits
for (int i = 0; i < 10; i++) {
// Cows are the minimum of the unmatched digit counts in secret and guess
cows += Math.min(secretCounts[i], guessCounts[i]);
}
// Return the result in the format "xAyB"
return bulls + "A" + cows + "B";
}
}