wretar's blog

By wretar, history, 4 weeks ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by wretar (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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:

    vector<vector<int>> 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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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