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.