0
$\begingroup$

I've been given a question to solve:

Given a set of non-negative distinct integers, and a value $m$, determine if there is a subset of the given set with sum divisible by $m$.

For this question the answer is here

I don't understand the part after if DP[j]==True
what is actually the intuition behind this code. Please explain in detail.

$\endgroup$
  • 1
    $\begingroup$ What do you make of the description at geeksforgeeks.org? $\endgroup$ – greybeard Sep 6 '20 at 6:13
1
$\begingroup$

Let f (i, k) = true if and only of there is a subset of the first k integers with a sum equal to i modulo m. As an example, if a[12] = 75, then f (i, 12) is true if and only if either f (i, 11) is true or f ((i-75) modulo m, 11) is true. And obviously f (i, 0) is true if and only if i = 0.

So if you have n integers, create a two dimensional array of size m * (n + 1), then fill array [i, 0] for all i, then fill array a [i, 1] for all i, and so on until you filled a [i, n] for all i. And there you have the solution.

Next you figure out how to do this without using an array of (n+1) * m elements, and you figure out when you can stop early because you know the answer already.

And I would be curious if there is any reason why these numbers would have to be a set.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.