algoadvance

Leetcode 299. Bulls and Cows

Problem Statement

You are playing the “Bulls and Cows” game with your friend.

You write 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.

The function to be implemented is:

public String getHint(String secret, String guess)

The input strings secret and guess are of equal length and contain only digits.

Example

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: 
[1 bull (8) and 3 cows]

Input: secret = "1123", guess = "0111"
Output: "1A1B"
Explanation: 
[1 bull (1) and 1 cow (1)]

Clarifying Questions

1. Can the input strings contain leading zeros?
   • Yes, both secret and guess can contain leading zeros as they are simply strings of digits.
2. Are there any constraints on the length of secret and guess?
   • The length of secret and guess will be the same and it’s guaranteed by the problem statement.
3. Is there a maximum length for secret and guess?
   • Typically, for coding challenges, you should assume the lengths could be reasonably large but within processing limits, up to thousands of characters.

Strategy

1. Count Bulls: First, iterate through the characters of secret and guess in parallel and count the number of bulls (i.e., correct digits in the correct position).
2. Count Cows: Use two frequency arrays to store the counts of unmatched characters from secret and guess. Then, iterate over these frequency arrays to determine the number of cows.
3. Construct the Hint: Combine the counts of bulls and cows into the required “xAyB” format.

Steps:

• Initialize two arrays to keep the frequency of unmatched characters for both secret and guess.
• Traverse secret and guess to find bulls and fill frequency arrays for the remaining characters.
• Traverse the frequency arrays to count cows.
• Return the formatted result.

Code

Here’s the implementation in Java:

public class BullsAndCows {
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int[] secretCount = new int[10];
        int[] guessCount = new int[10];

        for (int i = 0; i < secret.length(); i++) {
            char sChar = secret.charAt(i);
            char gChar = guess.charAt(i);
            if (sChar == gChar) {
                bulls++;
            } else {
                // Increase frequency counts for non-matching characters
                secretCount[sChar - '0']++;
                guessCount[gChar - '0']++;
            }
        }

        int cows = 0;
        // Calculate cows based on the minimum frequency of characters in unmatched characters.
        for (int i = 0; i < 10; i++) {
            cows += Math.min(secretCount[i], guessCount[i]);
        }

        return bulls + "A" + cows + "B";
    }

    public static void main(String[] args) {
        BullsAndCows solution = new BullsAndCows();
        System.out.println(solution.getHint("1807", "7810")); // Output: "1A3B"
        System.out.println(solution.getHint("1123", "0111")); // Output: "1A1B"
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the secret (or guess since they are of equal length). We traverse the strings a constant number of times.
• Space Complexity: O(1), since the space used for the arrays to count digits is fixed (size 10, since there are only 10 possible digits).

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?