Count the numbers without consecutive repeated digits

Question

Count the numbers without consecutive repeated digits

Asha loves mathematics a lot. She always spends her time by playing with digits. Suddenly, she is stuck with a hard problem, listed below. Help Asha to solve this magical problem of mathematics.

Given a number N (using any standard input method), compute how many integers between 1 and N, inclusive, do not contain two consecutive identical digits. For example 1223 should not be counted, but 121 should be counted.

Test Cases

7 => 7
1000 => 819
3456 => 2562
10000 => 7380

The code snippet that i submitted for the above challenge was given below

f(int n)
{
 int i=1;
 int c=n;
 for(; i<=n; i++)
 {
 int m=-1;
 int x=i;
 while(x)
 {
 if (x % 10 == m)
 {
 c--;
 break;
 }
 m = x % 10;
 x /= 10;
 }
 }
 return c;
}

When I submitted the above code in the competition a few days ago I ranked the First. but yesterday I was at no 10-11-13 and now I am ranked 13 right now.

What was my mistake? What should I improve so that my rank will be the first in competitive programming?

• 200_success: Cross-posted from Code Golf and Stack Overflow.
• JS1: How are entries ranked? By execution time? Smallest code (code golfing)?
• sthede: Small suggestion... you could test for x%100==0, that would tell you immediately that there is a repeat in the number.

Answer 1

The problem statement gives a great hint: mathematics. So do not brute force.

Fix the leading digit less than the leading digit of \$N\$ (including zero). For the next digit you have 9 choices (to avoid repetition). For the next digit you again have 9 choices, etc. The is, any leading digit less than the leading digit of \$N\$ gives \9ドル^k\$ "good" numbers.

With a leading digit equals to leading digit of \$N\$ you have less choices, because you have to stay below \$N\$. The best way to deal with is is to remove the leading digit of \$N\,ドル and apply the same logic to the remaining number.

For example, for \$N=3456\$ it works like this \3ドル \times 9^3 + 4 \times 9^2 + 5 \times 9 + 6 = 2562\$

Now convert it to the code.

Hint: you can also go right to left.