Find the minimum sum which is divisible by X and the sum can only be formed by selecting K numbers from an array of size A.

Test Case **A = 5**, **X = 5**, **K = 3**, **Numbers in the array — 1 2 3 4 5**

Solution (2+3+5)/5 = 2 (only and minimum triplet(K = 3) divisible by 5(X = 5))

I would really appreciate if anybody can give any idea or hint on how to solve the problem.

Auto comment: topic has been updated by wretar (previous revision, new revision, compare).And I will be more than happy if you will give the source of this problem. Please don't say it's an interview problem

There is no real source for this problem. I thought of this problem while solving problems related to subset sum on geeksforgeeks.org.

We can solve this problem using dp.

`dp[i][j] - min sum of j numbers which is divisible by X`

Lets make dp[X][K+1] and fill it with Infinities. Then assign dp[0][0] as 0 Now we can just iterate through the array of values and try to improve our answer. We can do it like this:

Link to my code: https://pastebin.com/XGyYci04

Your explanation is very clear...Thanks a lot!!