Ndtyjky

Given two lists, for example:

a = {0, 1, 0, 1, 0, 1} - 6 elements

b = {1, 1, 1, 0} - 4 elements

I need to find the: length of the longest contiguous sublists (made of one contiguous fragment of one of the lists) of the same length and parity of the summed elements of sublist.

For this example the answer is 3 (3rd, 4th, 5th element from the "a" list and 3 first elements from the "b" list).

Lists are in a fixed order. Values in a list are integers larger or equal 0.

I'm stuck with complexity of about O(n^2) in the worst case. Here's how I solved the problem.

  Starting with the length of the longest possible sublist (in example it is 4)

while (length > 0){

(here I use "for" loop) Finding possible parities of that length or till for at least one of the lists all parities, within some of possible sublists, are found (0 and 1)

If there are in both lists, sublists of the same parity then it is the answer; break; if not: length--; }

if there hasn't been found any answer then the answer is 0

Obviously there is more efficient way to solve this problem but I couldn't think of any neither find something which might help me.

Do you have any ideas? Maybe someone had similar problem here but I couldn't find it? If there is anything you will need to be clarified let me know.

If the problem needs clarification instead of down voting please ask for clarification. Thanks.

EDIT: Here are some other examples:

a = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} - 10 elements

b = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0} - 10 elements

Answer: 10

a = {0, 0, 0, 0, 0, 0, 0} - 7 elements

b = {0, 0, 0, 0, 0, 0, 0, 0} - 8 elements

Answer: 7

a = {0, 0, 0, 1, 0, 0, 0} - 7 elements

b = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0} - 10 elements

Answer: 3

a = {0, 1, 0, 0, 1, 1, 1} - 7 elements

b = {1, 1, 1, 0, 1, 0} - 6 elements

Answer: 6

Here's a partial answer and a direction for consideration. Let's say the distances, meaning the number of even numbers, between odd numbers, o, were distributed so:

| o <- 2 -> o <- 4 -> o <- 5 -> o <- 17 -> |

Notice that we can utilize any combination of contiguous blocks between the odds and set its parity based on if we include or exclude just one of either the left or right odd element. For example:

4 + 1 + 5 (±2) odd:

     o <- 4 -> o <- 5 -> o

  or

    [exclude] <- 4 -> o <- 5 -> [exclude]



4 + 1 + 5 (+1) even:

     [exclude] <- 4 -> o <- 5 -> o

  or

     o <- 4 -> o <- 5 -> [exclude]

But if we exclude an odd on either or both ends, we can then use the range extending in to the next odd:

[4..0] + 1 + 5 (+1) even:

  [exclude] <- 4 -> o <- 5 -> o



(+1) 4 + 1 + [0..5] even:

  o <- 4 -> o <- 5 -> [exclude]

So in fact, it may be more useful to look at which sequence lengths we cannot achieve since the count of those is either much smaller or can quickly be ranged. Let's look at some of your examples:

{0, 1, 0, 1, 0, 1}

Odd-sum lengths we cannot reach: 4

Even-sum lengths we cannot reach: 2, 6



{1, 1, 1, 0}

Odd-sum lengths we cannot reach: None

Even-sum lengths we cannot reach: 4





{0, 1, 0, 0, 1, 1, 1}

Unreachable even-sum lengths: None

Unreachable odd-sum lengths: 7



{1, 1, 1, 0, 1, 0}

Unreachable even-sum lengths: None

Unreachable odd-sum lengths: 6





{0, 0, 0, 1, 0, 0, 0}

Unreachable even-sum lengths: > 3

Unreachable odd-sum lengths: None



{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

Unreachable even-sum lengths: None

Unreachable odd-sum lengths: All

The examples you provided allow for trivial O(n) solutions using the method below. Could you (or someone) please provide at least one example that would force this method to be inefficient? (Thus maybe helping us improve it :)

It seems to me, as illustrated in my other partial answer, that the more variety or randomness one tries to introduce in an input, the more likely it is that an optimal match could be found quickly because of the paucity of or regularity in unavailable lengths.

Method:

We can can calculate in O(n) time and space a frequency list for odd occurrences and their indexes (these determine parity switches). Starting from each end of the full range, we can recursively collapse one or the other side to determine the possible range by jumping to the next occurence in this precalculated list. (For any fixed side, we can also binary-search for a range by bisecting the other side.)

For example:

b = [1,   1,   1,   0]

l: (0,1)(1,2)(2,3)



Odd length 3-4, indexes: 0-(2..3)

Even length (collapse left):

  2-3, indexes: 1-(2..3)





a = [0, 1, 0, 1, 0, 1]

l:    (1,1) (3,2) (5,3)



Odd length 5-6, indexes: (0..1)-5

Even length (collapse right or left):

  3-5, indexes: (0..1)-(3..4)



Next odd length (collapse right or left again):

  1-3, indexes: (0..1)-(1..2)

Since we have no match for length 4, the next best is 3.

a = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Trivial, full range matches.

a = [0, 0, 0, 0, 0, 0, 0]

b = [0, 0, 0, 0, 0, 0, 0, 0]

Trivial again, no odd lengths.

a = [0, 0, 0, 1, 0, 0, 0]

b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Trivial, just one choice of even lengths, collapse right or left for ranges 1-3.

a = [0, 1, 0, 0, 1, 1, 1]

b = [1, 1, 1, 0, 1, 0]

Trivial, no collapse needed, full even range immediately matches, a indexes: (0..1)-6, b indexes: 0-(4..5)