Bulls and Cows

XXX. Bulls and Cows

HashMap

String Processing

Problem Statement:

You are playing the Bulls and Cows game. The objective is to guess a secret number. The secret number and your guess both consist of digits. You need to provide feedback in the form of:

• A for bulls: the number of digits that are correct and in the correct position.
• B for cows: the number of digits that are correct but in the wrong position.

Write a function that takes the secret number and your guess as input and returns the feedback in the format "xAyB", where x is the number of bulls and y is the number of cows.

Algorithm:

The solution involves:

1. Iterate through the digits of the secret number and the guess simultaneously.
2. For each digit:
   • If the digits are equal, increment the bull count.
   • If the digits are not equal:
     • Use an array to track occurrences of each digit.
     • If the current digit from the secret was previously seen in the guess, it contributes to the cow count.
     • If the current digit from the guess was previously seen in the secret, it contributes to the cow count.
3. Return the result as a string in the format "xAyB".

Complexity:

Time Complexity: O(n), where n is the length of the secret (or guess).
Space Complexity: O(1), since the auxiliary space is fixed to the size of the array for digits (10 elements).

Java Implementation:

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0; // Number of digits that are correct and in the correct position
        int cows = 0; // Number of digits that are correct but in the wrong position
        int[] numbers = new int[10]; // Tracks occurrences of each digit

        for (int i = 0; i < secret.length(); i++) {
            int s = Character.getNumericValue(secret.charAt(i)); // Digit from secret
            int g = Character.getNumericValue(guess.charAt(i)); // Digit from guess

            if (s == g) { // Digit matches in value and position
                bulls++;
            } else {
                if (numbers[s] < 0) cows++; // Digit s was previously seen in guess
                if (numbers[g] > 0) cows++; // Digit g was previously seen in secret
                numbers[s]++; // Increment count for digit s
                numbers[g]--; // Decrement count for digit g
            }
        }

        return bulls + "A" + cows + "B"; // Construct and return the result string
    }
}