2
$\begingroup$

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

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

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.

Now construct the adjacency matrix.

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – asds_asds Nov 16 '19 at 15:20
  • $\begingroup$ $0$ is also an outneighbor of each vertex. $\endgroup$ – Ashwin Ganesan Nov 18 '19 at 9:30
  • $\begingroup$ you can modify the matrix acordingly. $\endgroup$ – asds_asds Nov 18 '19 at 14:43
0
$\begingroup$

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
$\endgroup$

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.