Calculate the number of combinations of a sequence of numbers in a particular order

I have a problem solving coding challenge when I have to calculate the number of combinations, numbers from 0 to 9, with the length n, with 2 rules -

- The first number cannot be 0

- Every other number can be 0 or must be divisible by the previous number (number 1 can not be used as divisor), for example [5.0], [1,0] or [2,8], [4,8], [3,6]

For example, if the length n were 2, number of combinations would be 23 - [1,0]...[9,0] + [2,4], [2,6], [2,8], [3,6], [3,9], [4,8] + [2,2]...[9,9]

The resulting response can be code in some programming language or a formula to calculate answer

• if a digit is 0 what values an the next digit take? – asds_asds Nov 16 '19 at 15:03

There is a neat way to solve this problem using graph theory.

First of all you need to decide the states and their transitions.

Example:-

2 ->[2,4,6,8]
3 ->[3,6,9] and so on.


Imagine each state to be a vertex in a graph and each transition to be a directed edge.

In your case it may look like:-

[[0,0,0,0,0,0,0,0,0,0],
[1,0,0,0,0,0,0,0,0,0],
[1,0,1,0,1,0,1,0,1,0],
[1,0,0,1,0,0,1,0,0,1],
[1,0,0,0,1,0,0,0,1,0],
[1,0,0,0,0,1,0,0,0,0],
[1,0,0,0,0,0,1,0,0,0],
[1,0,0,0,0,0,0,1,0,0],
[1,0,0,0,0,0,0,0,1,0],
[1,0,0,0,0,0,0,0,0,1]]


Note that over here the 1s represent that you can transition from the current state to that state.

Thus, if the 5th element of the 3rd row is 1 it means that you can go from 2to4.

Finding all permissible combinations of length n is equivalent to finding all the walks of length n in this graph.

(Adjacency_Matrix)^n results in a matrix of the same dimension where (i,j) denotes number of unique walks of length n between vertex i and j.

Since first element cannot be 0, you can sum up the values of this matrix for all (i,j) where i!=0. This would be your answer.

Matrix Exponentiation takes O(d^3 log(n)) time. d-> DImension of matrix(10).

The DP approach would take too much time for n>10^4. Since this approach is log(n) it will perform better for large values of n.

• Dynamic Programming approach works as well but I guess it would take O(n*d) time complexity where d->10. Depending upon the value of n you can choose what suits you well. – asds_asds Nov 16 '19 at 15:20
• $0$ is also an outneighbor of each vertex. – Ashwin Ganesan Nov 18 '19 at 9:30
• you can modify the matrix acordingly. – asds_asds Nov 18 '19 at 14:43

Can you solve the problem for $$n=1$$?
Can you deduce the answer for $$k+1$$, if you know the answer for $$k$$?
(hint: you need an $$n\times 10$$ table, the $$k$$-th row devoted for problem size $$k$$, the columns for partial answers...)

ps: I think that the answer is $$9+0+1+1+2+1+3+1+3+2=23$$ for n=2 (and 125 for $$n=3$$)

0: 10,...,90
1: -
2: 22
3: 33
4: 24,44
5: 55
6: 26,36,66
7: 77
8: 28,48,88
9: 39,99