Finding number of subsets of an array that add up to a multiple of a specific number

Question

I have an array A of length N of negative as well as positive integers. I need to count the number of subsets in this array which add up to a multiple of a number M (or 0 (mod M))
For example:

Let A = {1,2,8,4,5}, M = 9,
Then, there are 4 such subsets:

• {}: Empty set, corresponding to the multiple 0,
• {1,8}: corresponding to the multiple 9,
• {4,5}: corresponding to the multiple 9
• {1,8,4,5}: corresponding to the multiple 18.

I thought of generating all possible multiples and then applying dynamic programming subset sum, but the constraints won't allow me that.

Constraints:
1 =< N <= 10^5,
1 =< M <= 100,
-10^9 =< each entry of array <=10^9

What should be my approach for this sort of problem?

Answer 1

You can solve this problem by dynamic programming, albeit extensive for large M and fast for small M. For each j satisfying 0 <=j <= M-1, and each integer k satisfying 0 < k <= N, let f(k,j) be the number of subsets of array elements between 1 and k that add up to give a sum of j mod M. Then to extend the counter f(k,j) to f(k+1,j') for all j' you just need to take the (k+1)th element X in your sequence and set f(k+1,j') = f(k,j') + f(k,j' - X mod M). When you iterate over all j satisfying 0 <= j <= M-1 for each k and then successively iterate over all k satisfying 0 <= k <= N, you will get your answer at f(N,0). Total complexity is O(MN), which for small M is basically linear in N, optimal.