[C] 3ms Solution with explanation


  • 0
    K

    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.

    0_1488499918501_T_formula.PNG

    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){
                A++;
            }
            freq_s[ *(secret++) - '0' ]++;
            freq_g[ *(guess++) - '0' ]++;
        }
    
        for(i=0;i<10;i++){
            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.