algoadvance

Leetcode 299. Bulls and Cows

Problem Statement

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.

Given the secret number and your friend’s guess, return the hint in the format xAyB where x is the number of bulls and y is the number of cows.

Note:

• You may assume that the secret number and the friend’s guess have the same length and both contain only digits (0-9).

Clarifying Questions:

1. Should we check for any invalid input or can we consider the inputs are always valid?
   • Assume the inputs are always valid.
2. What should be the format of the output string?
   • The format should be xAyB where x is the number of bulls and y is the number of cows.

Strategy:

1. Initialize two counters - one for bulls, one for cows.
2. Use two arrays (or hash maps) to keep track of the frequency of digits in the secret and the guess that are not bulls.
3. Iterate through both strings simultaneously:
   • If the characters match, increment the bulls counter.
   • If the characters don’t match, update the frequency counts for both secret and guess.
4. After the first pass through the strings, for each digit (0-9), the potential cows can be determined by the minimum of the frequency counts in secret and guess.
5. Construct the result string in the format xAyB.

Time Complexity:

• One pass to count bulls and record frequencies (O(n)).
• One additional pass through the 10 possible digits for cows calculation (O(1)).
• Total time complexity is O(n).

Code:

#include <string>
#include <vector>
#include <algorithm>

std::string getHint(std::string secret, std::string guess) {
    int bulls = 0, cows = 0;
    std::vector<int> secretFrequency(10, 0), guessFrequency(10, 0);

    // First pass to count bulls and record frequencies
    for (int i = 0; i < secret.size(); ++i) {
        if (secret[i] == guess[i]) {
            ++bulls;
        } else {
            ++secretFrequency[secret[i] - '0'];
            ++guessFrequency[guess[i] - '0'];
        }
    }

    // Count cows
    for (int i = 0; i < 10; ++i) {
        cows += std::min(secretFrequency[i], guessFrequency[i]);
    }

    return std::to_string(bulls) + "A" + std::to_string(cows) + "B";
}

In the code:

• We use two arrays secretFrequency and guessFrequency to count occurrences of digits that are not in the correct position.
• The std::min(secretFrequency[i], guessFrequency[i]) gives us the number of cows for each digit.
• Finally, the result string is constructed and returned.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?