Find the longest contiguous subsequence such that its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$

Question

You are given $N$ $(1 \le N \le 10^6)$ positive integers $a_1, a_2, \ldots, a_N (1 \le a_i \le 10^6)$ and two positive integers $D$ $(1 \le D \le 10^6)$ and $M$ $(1 \le M \le 10^6)$

Find the longest contiguous subsequence such that

1. its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$, and
2. $(a_i + a_{i+1} + \cdots + a_j) \le D\cdot M$.

I can find the longest contiguous subsequence such that its sum is divisible by $D$, but I don't know how to include the second condition. Can anyone help me to solve this problem? I think it should work in something like $O(N)$ or $O(N \cdot \log N)$.

To find the longest contiguous subsequence such that its sum is divisible by $D$, I use the fact that $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$ if and only if $(a_1 + a_2 + \cdots + a_{i-1}) \mod D = (a_1 + a_2 + \cdots + a_j) \mod D$. So, I calculate prefix sum and for every possible remainder I remember when it first occured.

Answer 1

There exists a linear time algorithm.

1. Compute partial sum $s_j = \sum_{i=1}^j a_i$ and their remainders $r_j = s_j \mod D$.

2. Consider the sequence $\{(j,s_j,r_j)\}_{j=0}^N$. For each $0\leq r < D$, compute the subsequence consisting of all tuple $(j,s_j,r_j)$ such that $r_j = r$. An easy approach is to sort the tuples in the sequence by their third component, using an stable sorting algorithm ($O(N \log N)$ time). In this problem, $D \approx N$, so we could use bucket sort, improving the running time to linear; otherwise, using hash could also improve the running time to linear.

3. For each subsequence, apply the following algorithm on it.

   1. Pick two pointer $i,j$, both initialized as the first element in the subsequence.
   2. If $s_j - s_i > DM$, point $j$ to the successor of $(j,s_j,r_j)$ in the subsequence, otherwise point $i$ to the successor of $(i,s_i,r_i)$ in the subsequence.
   3. Repeat step 2 until $j$ points to the last element in the sequence.

   Among all temporary values of $(i,j)$, find one that maximize $j-i$ under constraint $s_j-s_i \leq DM$.