Counting numbers with specific digits

The challenge:


Suppose you are inhabitant of a planet where 1, 7, and 9 are lucky digits. A lucky number for you is a number that contains only your lucky digits in it. For ex: 1, 79, 911, 9917 etc., are lucky, where as 5, 172, 93, 170 are not. Given a integer N, count the number of lucky numbers in the range 1 to N.

[Constraints : 1 ≤ N ≤ 10^12. Time limit : 3s]

How can I make this code faster? As of now it exceeds way beyond 3 secs.

#include
#include
int lucky(long long int num)
{
    while(num>0)
    {
        if(!(num%10==1 || num%10==7 || num%10==9))
            return 0;
        num = num/10;
    }
    return 1;
}
int main()
{
    clock_t tic = clock();
    long long int num,i,count = 0;
    scanf("%lld",&num); 

    for(i=1;i<=num;i++)
    {
        count += lucky(i);
    }

    printf("%lld\n",count );
    clock_t toc = clock();

    printf("Elapsed: %f seconds\n", (double)(toc - tic) / CLOCKS_PER_SEC);
    return 0;
}

The trick to this problem is that you shouldn't check each number. It takes way too long.

An important thing I noticed is that there's only 3 digits that count. If N is 10, then there are 3 lucky numbers, because there are 3 lucky digits. And if N is 100, then there are 12 lucky numbers, because there are 3*3 combinations of lucky numbers. But there's 12 in total, because we write '01' and '07' and '09' as 1, 7 and 9.

So by looking at each digit of N, we can solve the problem faster.

Have a look at this table, where I wrote all the lucky numbers up to N = 1000.

1     7     9 = 3
 11    17    19 
 71    77    79
 91    97    99 = 12
111   117   119 
171   177   179 
191   197   199 
711   717   719 
771   777   779 
791   797   799 
911   917   919 
971   977   979 
991   997   999 = 39

Take N = 1000 with lucky digits 2, 7, 9.

This one is easy. 1000 means we score all the 3 digit numbers (which is 3 + 3^2 + 3^3). The first digit does not match a lucky digit, so we are done.

N = 1000 with lucky digits 1, 7, 9 is a tad harder to explain: First, we get all the 3 digit numbers because N is a 4 digit number. Next, since the first digit is a lucky digit, we need to score all the points you can make with the next digit. But because the next digit is not equal to or greater than a lucky digit, that score is 0.

N = 1150 with lucky digits: again, score 39 for having 4 digits. Next, score 150, but without taking the free score for having 3 digits. Since the first digit of 150 is a lucky digit but not greater than a lucky digit, you get 0 times all the 2 digit lucky numbers. So 0. 50, however, starts with 5. 5 is greater than 1, but smaller than 7, so you get 1 * the amount of lucky numbers with 1 digit. N = 1150, score is 42.

N = 1750:

• 39 points for being 4 digits (3 + 3^2 + 3^3)

• 1 is not bigger than any lucky digits, so 0 * 3^3

• 1 is a lucky digit, so continue with the next digit

• 750 starts with 7, 7 is bigger than 1 but not bigger than 7 or 9, so 1 * 3^2 = 9 points here

• 7 is a lucky digit, so continue with the next digit

• 50 starts with 5, 5 is bigger than 1 but not bigger than 7 or 9, so 1 * 3^1 = 3 points here

Makes for a total of 39 + 0 + 9 + 3. = 51.

N = 11:

• 3 points for being 2 digits (3)

• 1 is not bigger than any lucky digits, so 0 * 3

• 1 is a lucky digit, so continue with the next digit

• it's the last digit, so count each lucky digit the last digit is equal to or greater than as 1 points - in this case, that's only '1', so 1 point it is

So for N = 11, 4 lucky numbers.

N = 2000:

• 39 points for being 4 digits (3 + 3^2 + 3^3)

• 2 is bigger than 1 lucky digit, so 1 * (3^3) = 27

• 2 is not a lucky digit, so end there

makes 39 + 27 = 66.

Here's a table to check:

1     7     9 = 3
  11    17    19 
  71    77    79
  91    97    99 = 12
 111   117   119 
 171   177   179 
 191   197   199 
 711   717   719 
 771   777   779 
 791   797   799 
 911   917   919 
 971   977   979 
 991   997   999 = 39
1111  1117  1119 - 3
1171  1177  1179 - 6
1191  1197  1199 - 9
1711  1717  1719 - 12
1771  1777  1779 - 15
1791  1797  1799 - 18
1911  1917  1919 - 21
1971  1977  1979 - 24
1991  1997  1999 = 27 + 39 = 66

So, why does this matter?

Because this algorithm I just explained is about \$O(log n)\$. That is, N = 1000 takes 4 times as long as N = 1. N = 10^12 would take 12 times as long as N = 1.

Your algorithm is \$O(n)\$, as it checks each number. That means N = 1000 takes a thousand times (1000) as long as N = 1. This means that for the higher cases, your code takes too long, as N = 10^12 means your code takes 1.000.000.000.000 times longer to complete than for N = 1.

StackExchange Code Review Q#117592, answer score: 17