1
$\begingroup$

A sequence of positive integers $a_1, ..., a_n$ is given. Compute the length of the largest continuous subsequence such that the number of even integers is equal to the number of odd integers in the subsequence.

I have thought that we could take all those integers mod 2 and store those in an array, then take two pointers $i=0,j=n-1$ and somehow sweep the table until #(even) = #(odd) is found in the subsequence inside, so that $j-i+1$ would be the optimal length. But I don't know how exactly to choose which of the two pointers to increase/decrease each time, so that I get an $O(n)$ algorithm.

Is my algorithm on the track, or can't it be used here? What algorithm do I need to apply and how can I think of its idea? (It would be preferable if this problem could be solved without using special data structures, such as AVL, segment, suffix trees, etc.)

$\endgroup$
1
$\begingroup$

Here's an easy linear time solution which uses $O(n)$ space. You could probably bring this down to $O(1)$ space using the techniques you mentioned.

First compute $$ D_i = \# \text{even integers among $a_1,\ldots,a_i$} - \# \text{odd integers among $a_1,\ldots,a_i$}. $$ You can do this in $O(n)$.

Second, for each $\Delta \in \{-n,\ldots,n\}$, compute $a_\Delta = \min \{ i : D_i = \Delta \}$ and $b_\Delta = \max \{ i : D_i = \Delta \}$ (possibly these are undefined). You can do this in $O(n)$.

Finally, compute $\max_\Delta b_\Delta - a_\Delta$ for all $\Delta$ for which these indices exist. This also takes $O(n)$.

$\endgroup$
  • $\begingroup$ I really don't fully understand that algorithm... Can you rephrase it somehow please? First, what does "integers among first i" mean? Also, $a_Δ$ is an index, so $Δ$ is a subindex? And finally, by finding this maximum, what exactly is accomplished? $\endgroup$ – Jason Dec 18 '16 at 20:36
  • 2
    $\begingroup$ I improved the notation slightly. The end result is the length of the largest contiguous subsequence having an equal number of odd and even integers. I leave the rest for you to ponder. $\endgroup$ – Yuval Filmus Dec 18 '16 at 20:41

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.