I see some things that may help you improve your code. First, I'll mention some comments about the code you've already written and then present a better algorithm.
Use bool where appropriate
The return value for lucky should probably be a bool instead of an int. You can make that change easily by adding the line
#include <stdbool.h>
And then changing the routine to return bool.
Be careful with signed versus unsigned
By the problem description, num can't be less than 1, so it should probably be declared as long long unsigned rather than long long int which could be negative.
Use more whitespace
Your code can be a lot more readable if instead of this:
for(i=1;i<=num;i++)
You could write it like this:
for(i = 1; i <= num; i++)
The additional whitespace makes it easier to read and understand.
Isolate calculation from I/O
The main routine does both the input and output and also is materially involved in the main calculation which is to count lucky numbers. I'd advocate that that function should be isolated like this:
unsigned countLucky(long long unsigned num)
{
unsigned count = 0;
for(long long unsigned i = 1; i <= num; i++) {
count += lucky(i);
}
return count;
}
Only time the algorithm
The way the timing is done in the current program, it includes the time it takes for the user to type in the number as well as the time for the algorithm. The variability of human beings makes such data less useful than if the time were only for the algorithm.
Eliminate return 0 at the end of main
Since C99, the compiler automatically generates the code corresponding to return 0 at the end of main so there is no need to explicitly write it.
A better algorithm
Your existing code, while not the fastest possible, does have a significant advantage in that it is obviously correct. We can use that to verify any alternative approach as well as using it for timing comparisons. From here to the end of this review, I'll be showing stepwise improvements in the code.
Write a test harness
We might write several versions of the code and want to compare them. One nice way to do that is using a structure and a macro like this:
typedef struct {
unsigned (*fn)(long long unsigned num);
const char *name;
} counttest;
#define TEST(x) { x, #x }
Now we can easily make an array of tests and run through all alternative algorithms:
int main()
{
const counttest test[] = {
TEST(countLucky),
TEST(countLucky2),
};
const size_t tests = sizeof(test)/sizeof(test[0]);
long long unsigned num;
scanf("%llu",&num);
for (size_t i=0; i < tests; ++i) {
clock_t tic = clock();
unsigned count = test[i].fn(num);
clock_t toc = clock();
printf("%u\n%s: ",count, test[i].name);
printf("Elapsed: %f seconds\n", (double)(toc - tic) / CLOCKS_PER_SEC);
}
}
Think carefully about the problem
As others have pointed out, there is a way to make the running time on the order of \$O(\log n)\$. What hasn't yet been spelled out is how that actually translates into both a correct and efficient algorithm. So with that said, here's how we can do that.
First, note that for single digit numbers, the answer can be directly derived from a simple structure like this:
static const int k[10] = {
// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
0, 1, 1, 1, 1, 1, 1, 2, 2, 3
};
Also, we can enumerate the lucky numbers as follows:
lucky base-3
1 0
7 1
9 2
11 00
17 01
19 02
71 10
77 11
79 12
91 20
97 21
99 22
111 000
117 001
119 002
171 010
177 011
179 012
191 020
197 021
199 022
711 100
717 101
719 102
771 110
777 111
779 112
791 120
797 121
799 122
911 200
917 201
919 202
971 210
977 211
979 212
991 220
997 221
999 222
... and so on. There are 3 1-digit lucky numbers, 9 2-digit lucky numbers, 27 3-digit lucky number and so on. So there are \$3^n\$ \$n\$-digit numbers. For any number that is \$n+1\$ digits long, we add up each of these as \$\sum_{k=1}^{n} 3^k = \frac{3}{2}(3^n - 1)\$. Then the only part to account for is the number of \$n\$-digit numbers less than or equal to the given number.
To make it a bit more concrete, consider the number 157. You can see that 157 is between 119 and 171 in the chart above, and if you count, you can see that there are 15 lucky numbers less than or equal to 157.
That is, since 157 is a 3-digit number, we know that there are \$\frac{3}{2}(3^2 - 1) = 12\$ 2-digit lucky numbers less than 157, and then however many 3-digit lucky numbers are \$\le 157\$. As you may have guessed by the additional column in the table above, we can consider each lucky number as a base-3 number. Then all we need to do is find the base-3 number that corresponds to the number that is \$\le 157\$. We can do that by observing that we can almost convert the input number into the base-3 equivalent by the following algorithm:
m = base-3 equivalent of first digit
for each remaining digit "d"
m = 3 * m + base-3 equivalent of next digit
The problem with that is that if we have a number like 100, which is already less than the lowest 3-digit lucky number, it should contribute zero to the sum, while if the number is 112, there is exactly 1 3-digit lucky number less than it. Essentially, we have to account for a "borrow" from higher digits while converting. A fully worked (and correct) version of the code is this:
static const int MAXBUF = 20;
unsigned countLucky2(long long unsigned num)
{
static const int k[10] = {
// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
0, 1, 1, 1, 1, 1, 1, 2, 2, 3
};
char buff[MAXBUF];
int digits = snprintf(buff, MAXBUF, "%llu", num);
if (digits < 0) {
return 0; // encoding error
}
--digits;
unsigned count = 1;
int d = buff[0]-'0';
int m = k[d]-1;
bool borrow = (d != 1 && d != 7 && d != 9);
for (int i=1; i <= digits; ++i) {
int d = buff[i]-'0';
count *= 3;
if (borrow) {
m = 3*m + 3;
} else {
m = 3*m + k[d];
borrow = (d != 1 && d != 7 && d != 9);
}
}
return count + m;
}
Note that I've used Horner's rule to turn the exponentiation into a series of multiplications. This makes the code both relatively efficient and also requires no floating point routines.
Results
Here are some comparisons of the above code on my machine:
157
15
countLucky: Elapsed: 0.000003 seconds
15
countLucky2: Elapsed: 0.000003 seconds
11118888
3333
countLucky: Elapsed: 0.117209 seconds
3333
countLucky2: Elapsed: 0.000003 seconds
1234567890
36084
countLucky: Elapsed: 12.574423 seconds
36084
countLucky2: Elapsed: 0.000004 seconds
9876543210
82011
countLucky: Elapsed: 250.884767 seconds
82011
countLucky2: Elapsed: 0.000005 seconds
As you can see, both versions give the same answers, but the new version returns the answer in less than \$5\mu \text{s}\$.
