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 < 109).
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:
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 other cores available ? And maybe some enhanced algorithm you suggest :)