Bulls and Cows – LeetCode

This is the seventh question on our AlgoMaster Sheet. This involves Hashing concepts we have covered till now. If you haven’t followed our AlgoMaster sheet in a sequential manner, we highly recommend you check all the articles in a sequential manner otherwise you may feel lost!! The link to the Youtube Channel is- CS FOR ALL !!

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. Specifically, the non-bull digits in the guess could be rearranged such that they become bulls.

Given the secret number secret and your friend’s guess guess, return the hint for your friend’s guess.

The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.

Example 1:

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

Example 2:

Input: secret = "1123", guess = "0111"
Output: "1A1B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1123"        "1123"
  |      or     |
"0111"        "0111"
Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.

Constraints:

• 1 <= secret.length, guess.length <= 1000
• secret.length == guess.length
• secret and guess consist of digits only.

Intuition:

Let us look at a given example, to help us understand the question better. But before that let us have a clear knowledge of what we mean by Bulls and Cows in this question. The number of bulls is equal to the count of the number of characters(0 – 9) that are in the same position in both Secret as well as Guess strings respectively. Cows are those numeric characters(0 – 9) that are present in both Secret as well as Guess strings but are at different positions(indices) in the given string. Now with a clear understanding of what BULLS & COWS are- let us dive deep into an example and figure out how we can solve the question!!

Given secret = “1807” and guess = “7810”. Our output should come us “1A3B”. Let us examine how we have got this string. If we closely look at the Secret message – the characters at 1st Index(2nd Position), that is the digit 8 is appearing exactly at the same position or index in both Secret and Guess strings. So our count of Bulls stands at 1(One).

Similarly. if we try to find the count of cows- we will see that all the characters(or digits to be specific) have appeared both in Guess and Secret strings but are at the wrong positions. Thus our count of Cows stands at 3(Three). This example is pretty self-explanatory so we need to return “Count of Bulls” + A + “Count of Cows” + B as our final string.

Let us see another example that will help us to build our intuition even more- secret = “1123” and guess = “0111”. We can see that the digit at the 1st Index(2nd position) is matching thus our count of bulls, in this case, is 1(One).

However, the digit 1 also appears one more time in both secret and guess strings but they can be arranged correctly such that their positions also match. Thus, our count of cows is also 1(One) in this case. Thus our final string is- “1A1B” [“Count of Bulls” + A + “Count of Cows” + B].

From the discussion we have, we can see that finding the Count of Bulls is pretty simple- we need to look that if the i-th character in string Secret is the same as the i-th character in string Guess. This is how we can count the number of bulls in this question.

Similarly, to count the number of cows, we need to look for elements that are present in both present in Secret as well as Guess messages. This can be done with the help of hashing in this case- let me elaborate on how we can achieve this!!!

If we are looking for elements in both Secret and Guess messages- we can easily do that if we maintain a frequency array for both Secret and Guess strings separately. If we maintain that for all the characters not being a BULL- that is, all the digits that are not matching in their correct index can be stored in both stored in a freqG and freqS respectively. In the end, we can store cows += as the min(freqG[i], freqS[i]).

Algorithm:-

1. Declare an array of freqS[10] and freqG[10] to store the non-matching characters in both secret and guess strings respectively.
2. Iterate over string secret and check if the i-th character in secret and guess are the same or not.
3. If the secret[i] and guess[i] are the same, we increment the count of bulls by 1.
4. If they are not the same, we increment the freqS[] and freqG[] for that digit,
5. To get the count of cows, we traverse over the freqS[] and store the min(freqS[i] and freqG[i]). We store the minimum of freqS[] and freqG[] for any digit as we need to ensure that the particular digit is present in both Secret and Guess for the same number of times, that is, the frequency of that digit is the same.

Code:-

string getHint(string &secret, string &guess) 
    {
        int n = secret.size() ;

        // Array to store the frequency of digits in secret and guess
        int freqS[10] = {0} ;
        int freqG[10] = {0} ;

        int bulls = 0 ;

        for(int i = 0 ; i < n ; i++)
        {
            // Storing the digit from secret and guess
            int s = (int) (secret[i] - '0') ; 
            int g = (int) (guess[i] - '0') ;

            // Increasing the bull count if both the digits are same
            if(s == g)
                bulls += 1 ;

            else
            {
                // Storing the frequency in case the digits are difference
                freqS[s] += 1 ;
                freqG[g] += 1 ;
            }
        }

        int cows = 0 ;

        for(int i = 0 ; i < 10 ; i++)
            cows += min(freqS[i] , freqG[i]) ; // Adding the common digits present in both
        
        string ans = to_string(bulls) + "A" + to_string(cows) + "B" ;  // Printing the answer in required format

        return ans ;

    }

class Solution {
    public String getHint(String secret, String guess) {
        int n = secret.length();

        // Frequency array to store the frequency of digits in secret and guess
        int[] cowS = new int[10];
        int[] cowG = new int[10];

        int bulls = 0;

        for(int i=0; i<n; i++)
        {
            // Storing the digits from secret and guess
            int chr1 = secret.charAt(i) - '0';
            int chr2 = guess.charAt(i) - '0';
            
            // Increasing the bull count if both the digits are same
            if(chr1==chr2)
                bulls++;
            else
            {
                // Storing the frequency of each character which are different
                cowS[chr1]++;
                cowG[chr2]++;
            }
        }

        int cows = 0;

        for(int i=0; i<10; i++)
            cows = cows + Math.min(cowS[i],cowG[i]);  // Adding the characters which are common in both secret and guess

        String ans = bulls + "A" + cows + "B"; // Storing the answer in the required format

        return ans;
    }
}

Analysis of Time & Space Complexity:-

As we have traversed through the string Secret or Guess only once simultaneously, thus the Time Complexity is only Linear and is O(N). The Space Complexity is a bit difficult to analyze. Although we are using two external arrays the length of them is constant !! Why you can say right?? Think for a moment, the length of freqS[10] and freqG[10] is always 10 irrespective of the length of the given strings Secret or Guess. Thus, we can safely say that Space Complexity is O(10)!! BUT BUT BUT wait for a moment?? Does O(10) really makes sense?? In place of O(10), we can also say O(20) or O(100) anything right?? Thus following standard convention- we should say the Space Complexity is O(1) and is constant[ independent from the size of N].

If you have still any more doubts, make sure to check the following video by SUNYUL HOSSEN and also follow his YouTube Channel – CS FOR ALL for such amazing content!! For any questions, regarding the post, you can post down in the comment section!!

Contributors: Arghya Chatterjee: LinkedIn, Tanmay Dutta: LinkedIn, Raj Chowdhury: LinkedIn & Arjan Hazra: LinkedIn