 # INFOSYS SAMPLE QUESTIONS

Unique Birthday Gift: Can anyone help me with this ques?
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, a, …, 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.
Input:
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.

2 Likes

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]+ dp[k] + … +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[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…

1 =< n =< 100000 1 =< k =< n

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, a, …, 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.
Input:
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 arrays.
Sample cases:
Input Output Output description
2
1
2 The required length is 1, so there are only two possible arrays: 
and .
2
2
3 All possible arrays are [1, 1], [1, 2], [2, 2].
[2, 1] is invalid because 1 is not divisible by 2.
3
2
5 All possible arrays are [1, 1], [1, 2], [1, 3], [2, 2], [3, 3].
this is exact question plzz provide me code

why did you took mod of 1e7 for the else condition