Hackerrank Weekly Challenge #6 // Problem 2

Problem statement

You're given a sequence $A[1 \ldots n]$, of $n \leq 10^6$  positive integers and an integer $1 \leq k \leq 100$. The task is to return the number of consecutive subsequences of the input sequence whose sum of elements is divisible by $k$. We call these subsequences good. The full problem statement is here.

Solution

The first observation is that the number of good subsequences is not greater than $\binom {n} {2} + n$ which fits in 64-bit integer. I used a simple dynamic programming solution here. Let:

$dp[i][r] :=$ number of subsequences ending in A[i] whose sum of elements divided by $k$ gives a rest $r$. It's worth to mention, that $r < 100$, because $k \leq 100$.

It's easy to compute $dp[i][r]$ for any $r$ using $dp[i - 1]$ and $A[i]$, more precisely:

$dp[i][(r + A[i]) \mod k] := dp[i - 1][r]$

and

$dp[1][a[i] \mod k] := 1$ and $dp[1][r] := 0$ for any $r \neq a[i] \mod k$

The number of good subsequences is the sum of dp[i][0] for every $1 \leq i \leq n$.

The last observation is that we need only $dp[i - 1]$ table when computing $dp[i]$, so there is no need to store the whole table.

The time complexity of that solution is $O(n \cdot k)$, but one testfile contains at most 20 test cases, so in the worst case it makes about $2 \cdot 10^9$ operations per testfile which is quite big. Fortunately, as I thought, the time limit is not a problem for that solution, because of average test files.