I am thinking of a state as dp[i][0] and dp[i][1] and storing a sum till ith index with the first sum as including that element and second sum as not including that element. At the last, I would check if dp[n-1][0] or dp[n-1][1] is m. Am i thinking in right direction or not ?
Different DP state : Modulo Sum
@Vishal_234 Let n > m
Consider the m sums
S1 = a1
S2 = a1 + a2
S3 = a1 + a2 + a3
.
.
.
Sm = a1 + a1 + a3 + … + am
If none of these sums are a multiple of m, two of them (Si and Sj) have the same remainder with m.
Then, Si - Sj = S(i + 1) + S(i + 2) + … Sj = 0 (mod m).
Hence, if n > m, the answer is always yes.
Case 2, n < m
Let f(i, j) be true if a remainder of j is possible with the first i numbers.
f(i, j) = false if a remainder of j is impossible with first i numbers.
Now, we have two options with ai. Either we use it or we don’t.
If we don’t use it, then f(i, j) = true for all j, such that f(i - 1, j) = true.
If we use it then, f(i, ai%m) = true and f(i - 1, (j + ai)%m) = true.
Finally for the answer, check the value of f(last, 0).
One tricky thing to watch out for is write the line f(i, ai%m) = true AFTER f(i - 1, (j + ai)%m) = true.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.