Unique Birthday Gift: Can anyone help me with this ques?
Your birthday is coming soon and one of your friends, Alex, is thinking about a gift for you. He knows
that you really like integer arrays with interesting properties.He selected two numbers, N and K and decided to write down on paper all integer arrays of length K
(in form a[1], a[2], …, a[K]), where every number a[i] is in range from 1 to N, and, moreover, a[i+1] is
divisible by a[i] (where 1 < i <= K), and give you this paper as a birthday present.
Alex is very patient, so he managed to do this. Now you’re wondering, how many different arrays are
written down on this paper?
Since the answer can be really large, print it modulo 10000.
The first line contains an integer, n, denoting the maximum possible value in the arrays.
The next line contains an integer, k, denoting the length of the array.


what is the constraints on n and k ?

what I think is this

dp[i][j] denotes the answer for the ith position having value j

now i ranges from 1 to k , and j ranges from 1 to N
so the final answer would be dp[k][1]+ dp[k][2] + … +dp[k][N]
i.e we are standing at the kth position and we need to add the values which we can get at the kth position (at the kth position or the last position we can have 1 till N possible)

now the base case which is k=1 or the starting position

so dp[1][j] =1 where j lies from 1 till N

now the transition

since the previous position value must divide the current position value
so lets say if the current position value is j , then the previous position must be a divisor of j

dp[i][j]+= summation (dp[i-1][x]) where x is a divisor of j

1 Like

pastebin this is what I implemented , may be i can improve it by iterating on multiples , do tell me the constraints so that I can improve my soln @kritipandey18

1 Like

constraints were not given there.

oh anyways i will try to improve my soln and will let u know

Yes try optimizing it…

(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)