# 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<stdio.h>
#include<time.h>
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;
}

• As a general advice for programming challenge, when the input can be super-huge (like Constraints : 1 ≤ N ≤ 10^12), it is a hint that a good solution will not involve checking each and every possible number. See Pimgd's excellent answer for more details. – SylvainD Jan 22 '16 at 14:57

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.

• I kinda discovered this algorithm as I went, which made for a messy explanation. I hope you all understand my solution - if anyone has a way of explaining in an easier to understand way, lemme know and I'll try editing it in. – Pimgd Jan 22 '16 at 15:05
• This is the solution I also came up with, but I can't explain it in a better way, so +1 for now and in case I come up with a better explanation I'll tell you :) – Gentian Kasa Jan 22 '16 at 15:48
• I think I found a slightly more elegant way to solve the problem which is related to your approach. However, it's not compact enough to fit in a comment, so I wrote another answer. – lex82 Jan 31 '16 at 12:19
• @lex82 3^3 = 27. Check your calculator. – Pimgd Jan 31 '16 at 15:58
• @Pimgd, you are so right :-D Seems like I didn't pay too much attention to the content but only how to fix it. I thought it was a 3*3. I'll delete my previous comment. – lex82 Jan 31 '16 at 16:20

## 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

for(i=1;i<=num;i++)


You could write it like this:

for(i = 1; i <= num; i++)


## 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}$.

• Well done with the improved explanation. You've managed to convert it into code as well, something I wasn't quite capable of. – Pimgd Jan 23 '16 at 14:05

Why don't you build up the lucky numbers and count the results? You know 1, 7 and 9 are in fact lucky numbers...you can form a new lucky number by appending a lucky digit to a lucky number (numer * 10 + digit), as long as the result is < N.

You may just form the numbers this way, and count the results...

Let $n$ be the number of digits of $N$, which can be determined in $O(\ln N)$ time.

Let $l_{n-1}$ be the number of lucky numbers less than $N$ with $n-1$ digits, and $l_{n}$ be the number of lucky numbers less than $N$ with $n$ digits. The final answer will be

$$l = l_{n} + l_{n-1}.$$

All lucky numbers with $n-1$ digits are less than $N$; let's count them. If we only consider numbers with $k$ digits (i.e. numbers preceded by $k-1$ zeroes), then we just choose a lucky digit for each of the $k$ positions. Thus, there are $3^k$ possibilities. Doing this for each value of $k$, we get:

$$l_{n-1} = \sum_{k=1}^{n-1} 3^k = \frac12 (3^n - 3)$$

which can be computed in $O(\ln n)$ time through repeated squaring.

Now, let's count $l_n$, the number of lucky numbers with exactly $n$ digits that are less than $N$. We need to count $n-1$ numbers that are both less than $N$ and lucky. There is no closed formula for this AFAIK, so instead we do a simple recursive algorithm (making use of the counting we did in the above case):

# digits is the array of digits of N, i.e. str(N).split('')
def numLucky(digits):
n = len(digits) - 1
digit = digits.pop(0)
if digit == 1: return numLucky(digits)
if digit < 7: return 0.5*(3**n - 3)
if digit == 7: return 0.5*(3**n - 3) + numLucky(digits)
if digit == 8: return (3**n - 3)  # simplified from 2*0.5*(3**n - 3)
if digit == 9: return (3**n - 3) + numLucky(digits)


Basically, if the leading digit of $N$ (call it $d$) is not a lucky number, we just multiply the number of lucky digits less than $d$ (which will either be 1 or 2) times the formula computed above for the number of lucky numbers with a certain number of digits. If $d$ is a lucky digit, we need to consider lucky numbers starting with $d$, which may or may not be less than $N$. Thus we recurse. The runtime is the number of digits of $N$, so $O(\ln N)$.

• Have you tested your algorithm? I think there's a problem in that it would seem to give the same answer for 100 as for 118 which is not correct. – Edward Jan 23 '16 at 1:46
• It would not. I think you are assuming that the code I gave is the whole algorithm; it is only the algorithm for the second part, as the first part is just basic math. You have to add the two results together; I'll edit to make that more clear. – gardenhead Jan 23 '16 at 3:59
• I think there's still a problem. First, it's not clear in the code how or when n is updated. Second, if you try the single-digit number 5 I think you'll see that the algorithm is incomplete. Try testing your code. – Edward Jan 23 '16 at 13:38
• What is n in your Python pseudocode? – 200_success Jan 24 '16 at 0:47

Other answers already showed that you can solve the problem in $O(log N)$ compared to $O(N)$ when you don't actually count the numbers but sum up the numbers of possible combinations of 1, 7, and 9 of different length. When looking for a simplification of the other approaches, I found out that it helps a lot to transform the problem a bit so you can work with base 3 numbers.

I came up with this algorithm:

1. Find the maximum number $m$ with $m \leq N$ so that $m$ is a lucky number. Let $d$ denote the number of decimal digits of this number.

2. Transform $m$ by replacing its digits according to the following mapping:

$\{ \; 1 \rightarrow 0, \;\; 7 \rightarrow 1, \;\; 9 \rightarrow 2 \; \}$

3. Treat the result as a base 3 number and add the base 3 number that consists of $d$ ones.

After step 3, you are already looking at the result. However, you might want to convert it back to base 10.

Please note, that the number may lose a digit in step 1 (e.g. when N is a power of 10). You can easily find $m$ by checking the digits of $N$ from left to right. When you encounter a digit that is not a lucky digit, reduce it to the next lucky digit and set the remaining digits (to the right) to 9. If the digit in question cannot be reduced (a zero) seek to the left until you find a digit you can reduce (7 or 9). If you find one, reduce this one instead and set all subsequent digits to 9. If you don't find one (apparently the first digit is a 1), omit the first digit and set all remaining digits to 9.

Explanation

Probably the easiest way to understand this is to look at an example: Let's take $N = 775_{10}$. The next lower lucky number is $771_{10}$ which according to our mapping translates to $110_3$. How does this help? Well, if we consider all ternary numbers lower than $110_3$ they give us all the other 3-digit lucky numbers lower than $771_{10}$ if we reverse the mapping again. Example: $012_3$ translates to $179_{10}$. Note that also $000_3$ stands for a 3-digit lucky number, namely $111_{10}$. This is why we have to correct our intermediate result of $110_3$ by adding one.

We are also missing the lucky numbers with only one and two digits. There are $010_3$ one-digit and $100_3$ two-digit lucky numbers. So in total we can just add $111_3$ to the intermediate result of $110_3$ to make up for all the numbers we missed in the first step . We obtain $221_3 = 25_{10}$.

There are a lot of good answers here, but most of them address your algorithm. I want to make the (incorrect) assumption that your algorithm is fine and focus on some readability issues your code has.

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;
}


First, let's talk just about the function signature:

int lucky(long long int num)


What does this method do? I know there's not a default boolean type in C, but there are plenty of good ways to introduce one. We should do this in order to make it clear that our method returns a true or false value only. And with that said, functions that return boolean type values read a little bit better with an is prefix. And finally, since I personally have such a hard time remembering how big things like long long int actually are, I also like to create type definitions here.

typedef long long int int64_t;


I also don't see a particularly good reason to abbreviate the parameter. So now we're looking at a signature which actually looks more like this:

bool isLucky(int64_t number);


Now it's clear. isLucky takes a 64-bit integer called number and returns a bool which should indicate whether or not that number is actually lucky or not.

As a side note, we may want to only accept unsigned integers. In which case our type definition and function signature become:

typedef long long unsigned uint64_t;
bool isLucky(uint64_t number);


Now, let's look at the function body.

while(num>0)
{
if(!(num%10==1 || num%10==7 || num%10==9))
return 0;
num = num/10;
}
return 1;


We've used a while loop, but the value we're using for our conditional is also being updated within the method body. Any time this is happening, I prefer to use a for loop:

for(; number > 0; number /= 10) {
if(!(number%10==1 || number%10==7 || number%10==9)) {
return false;
}
}
return true;


Using the for loop, it's more clear what's happening to the number on each iteration of the loop. The importance of this increases as the complexity of the loop's body increases. With a for loop, we can generally see exactly what's going to happen within a single line.

Importantly, you'll also notice that I've added braces around your if statement. Omitting braces around if statements (or anywhere) should never be considered optional (no matter what the compiler thinks) because it leads to bugs.