# Count the numbers without consecutive repeated digits

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?

• Cross-posted from Code Golf and Stack Overflow. Apr 21 '17 at 13:04
• How are entries ranked? By execution time? Smallest code (code golfing)?
– JS1
Apr 21 '17 at 17:11
• Small suggestion... you could test for x%100==0, that would tell you immediately that there is a repeat in the number. Apr 21 '17 at 18:45

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$