Search code examples
algorithmintegerdigitssubsequence

Count integers up to n that contain the digits 2018 in order

Given an integer n between 0 and 10,0000,0000, count the number of integers smaller than n which contain the digits [2,0,1,8] in order.

So e.g. the number 9,230,414,587 should be counted, because removing the digits [9,3,4,4,5,7] leaves us with [2,0,1,8].

Example input and output: 

n = 2018      ->  count =     1
n = 20182018  ->  count = 92237

My general thought is that: the maximum length of n is 10 and the worst situation is that we have to insert 6 digits into [2,0,1,8] and remove the duplicates and the numbers greater than n.

Solution

  • I don't see any own attempts to solve, so I'll give only clue:

    You have 9-digits number (small numbers might be represented as 000002018) containing digit sequence 2,0,1,8.
    Name them 'good' ones.
    Let denote digit places from 1 to 9 right to left:

         number     532705183
digits     5  3  2  7  0  5  1  8  3
index      9  8  7  6  5  4  3  2  1

    The most left '2' digit can occupy places from 4 to 9. How many good numbers contain the first 2 at k-th place? Let make function F2(l, k) for quantity of good numbers where 2 refers to digit 2, l is number length, k is place for the most left digit.

     .   .   .   .  2   .   .   .   .
                ^ 
                | 
 left part      k     right part should contain 0 1 8 sequence
 without 2's

 F2(9, k) = 9^(9-k) * Sum(F0(k-1, j) for j=1..k-1)

    Overall quantity of good numbers is sum of F2(9, k) for all possible k.

    GoodCount = Sum(F2(9, k) for k=4..9)

    Explanation:

    There are 9-k places at the left. We can put any digit but 2 there, so there are 9^(9-k) possible left parts.

    Now we can place 0 at the right part and count possible variants for 018 subsequences. F0(...) will of course depend on F1(...) and F1 will depend on F8(...) for shorter numbers.

    So fill tables for values for F8, F0, F1 step-by-step and finally calculate result for digit 2.

    Hand-made example for 4-digit numbers containing subsequence 1 8 and k = position of the first '1':
    k=2: there are 81 numbers of kind xx18
    k=3: there are numbers of kind x1x8 and x18x
    there are 9 subnumbers like x8, 10 subnumbers 8x, so (10+9)*9=171
    k=4: there are numbers of kind
    1xx8 (9*9=81 such numbers),
    1x8x (9*10=90 numbers),
    18xx (100 numbers),
    so 81+90+100=271
    Overall: 81+171+271=523