Finding all contiguous sublists such that each member appears an even number of times

The program needs to find all contiguous sublists of numbers where the number of occurrences of every member in the contiguous sublist is divisible by 2.

The first line of input is N (the number of ai, where N ≤ 353535). The second line of input contains the ai, delimited by spaces (where each ai 9).

Here is an example of input and what the output should be:

# N is the user input, and a is the user input with 
#numbers separated by space and converted to list with .split(" ") but
#we'll look for examles first :
N = 8 
a = [3,5,3,5,9,9,5,3]

The output of this input should be 5 because there are 5 contiguous sublists that meet the conditions:

• [3,5,9,9,5,3]

• [3,5,3,5,9,9]

• [5,9,9,5]

• [3,5,3,5]

• [9,9]

Here is my solution:

import time
total = 0
try:
    listlength = int(raw_input("Enter the number of list elements >> "))
    listofnumbers   = raw_input("Enter the list elements , space separated >>").split(" ")
    start = time.clock()
    for i in range(listlength,1,-1):
        for i1 in range(0,listlength + 1 - i):
            numbers = []
            countofnumbers=[]
            currentlist = listofnumbers[i1:listlength-abs(i-listlength+i1)]
            #print "I:",i,",TR nIZ ",tr_niz
            for k in currentlist:
                if k not in numbers:
                    numbers.append(k)
                    countofnumbers.append(currentlist.count(k) if currentlist.count(k)%2==0 else 0)
            if 0 not in countofnumbers:
                if sum(countofnumbers)%2==0:
                    total+=1

    print total
    print "Time: ",time.clock()-start

except ValueError:
    print "Data wrong"

My script solves small test cases really well. However, when there are 350350 numbers, It was working all the night, and it didn't turn up with result. How can I fix my algorithm to finish in a reasonable amount of time? Maybe implement multiprocessing because it's using 100% od my core when running , but doesn't use any of 3 o

The algorithm can be slimmed by tracking only those numbers for which the number of occurrences in the current window is unbalanced (i.e. odd). Whenever this auxiliary structure is empty, everything is balanced and the current window can be added to the set of solutions. Here's some pseudo code to illustrate the approach:

static void print_balanced_contiguous_subsequences (int[] a)
{
    var unbalanced = new HashSet();

    for (int i = 0, e = a.Length - 1; i < e; ++i)
    {
        unbalanced.Clear();

        for (int j = i; j <= e; ++j)
        {
            if (unbalanced.Contains(a[j]))
                unbalanced.Remove(a[j]);
            else
                unbalanced.Add(a[j]);

            if (unbalanced.Count == 0) // print the newly found sequence
                for (int k = i; k <= j; ++k) 
                    Console.Write("{0}{1}", a[k], k < j ? ' ' : '\n');
        }
    }
}

However, this algorithm is still quadratic in n (20 ms for 1000 elements, 2 seconds for 10000) and the key idea for a proper solution still eludes me...

The original problem description might contain a clue, or some restriction that can be leveraged to design a faster solution. It would be nice if it could be quoted verbatim in the question, or at least linked (even if it is not in English).

StackExchange Code Review Q#124218, answer score: 3