Eg.
$X = 3$ (allowed digits $1-3$ and digit limit ($1-9$))
$N = 2$
$(12), (13), (11), (23), (21), (32), (31)$
ans $= 7$
I tried to calculate the answer but the complexity to find the answer is O(n)
like in this case
count of co-primes for 1 is 3 (1,2,3), 2 is 2 (1,3), 3 is 2 (1,2)
ans(n) denotes answer for n digit number
dp(i,n) denotes answer for n digit number ending with i.
ans(2) = dp(1,2)+ dp(2,2) + dp(3,2)
dp(1,1)=1, dp(2,1) =1, dp(3,1)=1 (base case since there is only 1 way to form 1 digit number ending with a particular number)
dp(1,2) = dp(1,1)+dp(2,1)+dp(3,1) ( sum of all co-prime digit dp(i,n-1) )
dp(2,2) = dp(1,1)+dp(3,1)
dp(3,2) = dp(1,1)+dp(2,1)
ans(2) = 3 + 2 + 2
ans = 7
can we do this with a better time complexity?
Best Answer
Yes, you can find a closed form by using the techniques of linear recurrence relations. You have a set of coupled recurrence relations, which you can write as $$dp(i,n)=\begin {pmatrix}1&1&1\\1&0&1\\1&1&0\end{pmatrix}dp(i,n-1)$$ where $dp(i,n)$ is a column vector with $i$ being the last digit and $n$ the number of digits. You start with $dp(i,1)=\begin {pmatrix}1\\1\\1\end {pmatrix}$ because you can use any digit in the first position. You can diagonalize the matrix and find its eigenvalues and eigenvectors. The dominant eigenvalue is $1+\sqrt 2$, so the total number of numbers increases by about that factor each time. The other two eigenvalues are $-1, 1-\sqrt 2$, so $ans(n)=a(1+\sqrt 2)^n+b(-1)^n+c(1-\sqrt 2)^n$ where you can find $a,b,c$ from the first three values