We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Bulls and Cows

Difficulty: Medium

Problem 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 number of "bulls" (correct digits in the correct position) and "cows" (correct digits in the wrong position). Given the secret number and your friend's guess, return the hint formatted as "xAyB", where x is the number of bulls and y is the number of cows.

Key Insights

  • Bulls are counted as digits that match in both value and position.
  • Cows are counted as digits that match in value but not in position.
  • Both secret and guess can have duplicate digits, which affects cow counting.
  • A hash table can be used to count occurrences of digits to facilitate cow counting.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the secret and guess strings. Space Complexity: O(1), since the size of the hash table is limited to 10 (digits 0-9).

Solution

To solve the problem, we can use the following approach:

  1. Initialize counters for bulls and cows.
  2. Use two arrays (or hash tables) to count the occurrences of digits in both the secret and guess strings.
  3. First, iterate over both strings to count bulls and fill the occurrence counters for non-bull digits.
  4. Then, for each digit in the occurrence counters, calculate the number of cows by taking the minimum count of each digit present in both the secret and guess.
  5. Format the result as "xAyB" where x is the number of bulls and y is the calculated number of cows.

Code Solutions

def getHint(secret: str, guess: str) -> str:
    bulls = 0
    cows = 0
    secret_count = [0] * 10
    guess_count = [0] * 10

    # First pass to count bulls and fill counts for cows
    for s, g in zip(secret, guess):
        if s == g:
            bulls += 1
        else:
            secret_count[int(s)] += 1
            guess_count[int(g)] += 1

    # Second pass to count cows
    for i in range(10):
        cows += min(secret_count[i], guess_count[i])

    return f"{bulls}A{cows}B"
← Back to All Questions