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?

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.