2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you use dynamic programming approach to find the longest contiguous sub-sequence such that it's sum is divisible by D, then at every step you can also check whether the quotient Q <= M. D.Q = sum, and D.Q <= D.M $\endgroup$ – Sagnik Dec 15 '15 at 15:03
  • $\begingroup$ Can you describe how you find the longest contiguous subsequence such that its sum is divisible by D? $\endgroup$ – miracle173 Dec 16 '15 at 7:17
2
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ can you explain why the algorithm finds the $(i,j)$ that maximizes $j-i$ under the constraint? $\endgroup$ – miracle173 Dec 17 '15 at 10:06
  • $\begingroup$ You can also use counting sort in step 2 to obtain a deterministic linear time algorithm. $\endgroup$ – Yuval Filmus Dec 17 '15 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.