SHA1 checksum with K leading zeroes

I am trying to find the super efficient way to generate an random string for the equation below:

checkSum = SHA1(fixed_string + random_string)

The checksum has to have k leading zero to satisfy the final condition. The current implementation is using brute force methodology combined with the random string generator. But this method is kind of inefficient and time consuming if the K is bigger than 7.

static void
gen_random(char *s) {
    static const char alphanum[] =
        "0123456789"
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "abcdefghijklmnopqrstuvwxyz";

    for (size_t i = 0; i < LENGTH - 1; ++i) {
        s[i] = alphanum[rand() % (sizeof(alphanum) - 1)];
    }
}

Has anybody any idea to develop an efficient algorithm for generating random string to handle the condition in efficient way? The Other question is about the length of (fixed_string + random_string). What is the best length to handle the SHA1 check sum correctly?

Thanks