Count the number of subsequences with a given k modulo sum

Question

Given an array a of n integers, calculate how many subsequences (also non-sequential) have sum % k = 0 :

 1 <= k < 100 1 <= n <= 10^6 1 <= a[i] <= 1000 

The solution An O(n^2) easily possible, however, a faster method O(n log n) or O(n) needed.

Answer 1

This is a problem with a subset of the sum .

A simple solution is the following:

 s = 0 dp[x] = how many subsequences we can build with sum x dp[0] = 1, 0 elsewhere for i = 1 to n: s += a[i] for j = s down to a[i]: dp[j] = dp[j] + dp[j - a[i]] 

Then you can simply return the sum of all dp[x] , so x % k == 0 . This has a high complexity: near O(n*S) , where S is the sum of all your elements. The dp array should also have size S , which you probably can't even afford to declare for your limitations.

The best solution is to not iterate over amounts greater than or equal to k in the first place. For this we will use 2 dp arrays:

 dp1, dp2 = arrays of size k dp1[0] = dp2[0] = 1, 0 elsewhere for i = 1 to n: mod_elem = a[i] % k for j = 0 to k - 1: dp2[j] = dp2[j] + dp1[(j - mod_elem + k) % k] copy dp2 into dp1 return dp1[0] 

Whose complexity is O(n*k) and is optimal for this problem.

Answer 2

There is an O(n + k^2 lg n) -time algorithm. Compute the histogram c(0), c(1), ..., c(k-1) input array mod k (i.e. there are elements c(r) that r mod k ). Then calculate

  k-1 product (1 + x^r)^c(r) mod (1 - x^k) r=0 

as follows, where the constant member of the reduced polynomial is the answer.

Instead of evaluating each factor with a quick exponentiation method and then multiplying, we turn things inside out. If all c(r) are zero, then the answer will be 1 . Otherwise recursively evaluate

  k-1 P = product (1 + x^r)^(floor(c(r)/2)) mod (1 - x^k). r=0 

and then calculate

  k-1 Q = product (1 + x^r)^(c(r) - 2 floor(c(r)/2)) mod (1 - x^k), r=0 

in time O(k^2) for the last calculation, using sparseness of factors. The result is P^2 Q mod (1 - x^k) , calculated from the time O(k^2) by naive convolution.

Answer 3

Traverse a and counter a[i] mod k ; there must be k such samples.

Reserve and memoize over separate partitions k, 2*k, 3*k...etc. with parts less than or equal to k , adding the products of the corresponding counters.

For example, if k were 10 , some of the sections would be 1+2+7 and 1+2+3+4 ; but while memoizing, we only need to calculate how many mod k pairs in the array will produce (1 + 2) .

For example, k = 5, a = {1,4,2,3,5,6} :

 counts of a[i] mod k: {1,2,1,1,1} products of distinct partitions of k: 5 => 1 4,1 => 2 3,2 => 1 products of distinct partitions of 2 * k with parts <= k: 5,4,1 => 2 5,3,2 => 1 4,1,3,2 => 2 products of distinct partitions of 3 * k with parts <= k: 5,4,1,3,2 => 2 answer = 11 {1,4} {4,6} {2,3} {5} {1,4,2,3} {1,4,5} {4,6,2,3} {4,6,5} {2,3,5} {1,4,2,3,5} {4,6,2,3,5}