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;

            if (x % 10 == m)
            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?

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

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.