algoadvance

You are playing the Bulls and Cows game with your friend. You write down a secret number, and your friend tries to guess it.

The game follows these rules:

• Every time your friend makes a guess, you provide a hint that indicates how many digits in the guess match the number exactly in both digit and position (called “bulls”) and how many digits match the number but locate in the wrong position (called “cows”).
• The secret number and friend’s guess both contain only digits from ‘0’ to ‘9’.

Given the secret number and your friend’s guess, return a hint. The hint should be formatted as “xAyB”, where x is the number of bulls and y is the number of cows.

Examples

• Input: secret = “1807”, guess = “7810” Output: “1A3B”
• Input: secret = “1123”, guess = “0111” Output: “1A1B”

Clarifying Questions

1. Can the secret number or guess have leading zeros?
2. Are the lengths of the secret number and guess always the same?
3. Should the characters in the secret and guess always be numeric digits?

Strategy

1. Iterate through both secret and guess simultaneously to count bulls (same position and same digit).
2. Use an array to keep track of the frequency of each digit in secret and guess for cow counting:
   • If a position’s digits in both secret and guess are different, update the frequency.
3. Compare the frequency arrays to count the cows.
4. Build the result string in the form “xAyB” based on the number of bulls and cows.

Code

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

    for s, g in zip(secret, guess):
        if s == g:
            bulls += 1
        else:
            secret_counts[int(s)] += 1
            guess_counts[int(g)] += 1

    for i in range(10):
        cows += min(secret_counts[i], guess_counts[i])

    return f"{bulls}A{cows}B"

Time Complexity

• Time Complexity: O(n), where n is the length of the input strings secret and guess. We iterate over the strings a constant number of times (a few counts and comparisons).
• Space Complexity: O(1), since we use two fixed-size (length 10) lists for counting digits, which does not grow with the input size.

This approach efficiently calculates the number of bulls and cows by leveraging simple counting and iteration, ensuring clarity and performance.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?