{x}
blog image

Bulls and Cows

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.

Solution Explanation for Bulls and Cows

The problem involves comparing a secret code with a guess and determining the number of "bulls" (correct digits in the correct position) and "cows" (correct digits in the wrong position). The solution uses a counting approach for efficient processing.

Algorithm:

  1. Initialization:

    • Create two arrays (or hash maps) cnt1 and cnt2 to store the frequency of each digit (0-9) in the secret and guess strings, respectively. Initialize them to zero.
    • Initialize a variable bulls (or x) to 0 to count the bulls.

  2. Bulls Count:

    • Iterate through the strings secret and guess simultaneously using zip (Python) or a single loop with an index (other languages).
    • If the digits at the current position are the same (secret[i] == guess[i]), increment bulls.

  3. Cows Count:

    • For digits that are not bulls, increment their counts in cnt1 and cnt2.

  4. Cows Calculation:

    • Iterate through the digits (0-9). For each digit:
      • Find the minimum of its counts in cnt1 and cnt2. This represents the number of times that digit appears in both the secret and guess but in the wrong position.
      • Add this minimum count to the cows (or y) count.

  5. Result:

    • Return the result in the format "xA yB", where x is the number of bulls and y is the number of cows.

Time Complexity: O(n), where n is the length of the strings. We iterate through the strings once to count bulls and once to count cows. The operations within the loops are constant time.

Space Complexity: O(1). We use fixed-size arrays (cnt1 and cnt2) of size 10 (for digits 0-9), so the space used is constant regardless of the input string length.

Code Examples (with detailed comments):

Python:

from collections import Counter
 
class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        """
        Counts bulls and cows in a Bulls and Cows game.
 
        Args:
            secret: The secret code string.
            guess: The guessed code string.
 
        Returns:
            A string in the format "xA yB" indicating bulls and cows.
        """
        bulls = 0  # Initialize bull count
        cnt1 = Counter()  # Frequency counter for secret digits
        cnt2 = Counter()  # Frequency counter for guess digits
        
        # Count bulls and record non-bull digit frequencies
        for i in range(len(secret)):
            if secret[i] == guess[i]:
                bulls += 1
            else:
                cnt1[secret[i]] += 1
                cnt2[guess[i]] += 1
        
        # Count cows
        cows = 0
        for digit in cnt1:
            cows += min(cnt1[digit], cnt2.get(digit, 0)) # Handle case where digit might not be in cnt2
 
        return f"{bulls}A{cows}B"  # Format the output string

Java:

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0; // Initialize bull count
        int[] cnt1 = new int[10]; // Frequency array for secret digits
        int[] cnt2 = new int[10]; // Frequency array for guess digits
 
        // Count bulls and record non-bull digit frequencies
        for (int i = 0; i < secret.length(); i++) {
            int s = secret.charAt(i) - '0'; //convert char to int
            int g = guess.charAt(i) - '0'; //convert char to int
            if (s == g) {
                bulls++;
            } else {
                cnt1[s]++;
                cnt2[g]++;
            }
        }
 
        // Count cows
        int cows = 0;
        for (int i = 0; i < 10; i++) {
            cows += Math.min(cnt1[i], cnt2[i]);
        }
 
        return bulls + "A" + cows + "B"; // Format the output string
    }
}

The other languages (C++, Go, TypeScript, PHP) follow a very similar pattern, using arrays or maps to count digit frequencies. The core logic remains consistent across all implementations.