### wretar's blog

By wretar, history, 5 weeks ago, ,

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.

• 0

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by wretar (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 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
•  » » 5 weeks ago, # ^ |   0 There is no real source for this problem. I thought of this problem while solving problems related to subset sum on geeksforgeeks.org.
 » 5 weeks ago, # |   +1 We can solve this problem using dp. dp[i][j] - min sum of j numbers which is divisible by XLets 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:  vector> pre_dp = dp; int d; cin >> d; for(int i = 0; i < X; i ++){ // we iterate over dp ans try to minimize our sum for(int j = 1; j <= K; j ++){ pre_dp[(i+d) % X][j] = min(dp[(i+d) % X][j], dp[i][j-1] + d); } } dp = pre_dp; Link to my code: https://pastebin.com/XGyYci04
•  » » 5 weeks ago, # ^ |   0 Your explanation is very clear...Thanks a lot!!