[C] 3ms Solution with explanation

  • 0

    In one pass, we can actually collect all the information we need for the number of "bulls" and "cows".

    == Variables ==
    Let's first define the following:
    n = len(secret = len(guess) (since the assumption here is that both secret and guess are of the same length).
    A = # of bulls
    B = # of cows.
    T = A + B (Total # of correct digit guesses regardless of position)

    == Number of Bulls (A) ==
    This one is easy. As we traverse both secret and guess, if secret[i]==guess[i], then we increment A by 1. After the completing the traverse A would contain the number of bulls.

    == Number of Cows (B) ==
    As we traverse secret and guess, we can keep track of the frequency in which the digits "0"-"9" appears in both strings and store it in their respective arrays freq_s[10] and freq_g[10]. At the end, we tally up the frequencies, accumulating the mins of each digit frequencies. This gives us T, the total number of correct digit guesses regardless of position. I.e.


    Finally, B = T - A.

    The code is as follows:

    char* getHint(char* secret, char* guess) {
        char temp[50];
        char* hint;
        int freq_s[10] = {0};
        int freq_g[10] = {0};
        int A = 0;
        int B = 0;
        int i;
        while( *secret != '\0' ){
            if(*secret == *guess){
            freq_s[ *(secret++) - '0' ]++;
            freq_g[ *(guess++) - '0' ]++;
            B += (freq_s[i] < freq_g[i])? freq_s[i] : freq_g[i];
        B -= A;
        sprintf(temp, "%dA%dB", A, B);
        hint = (char*)calloc( strlen(temp)+1 , sizeof(char));
        strcpy(hint, temp);
        return hint;    

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.