Optimization hashing into arrays

So I came across this problem of basically finding n(n+1)/2 of numbers in an array where n is the frequency of the number.

Eg. 1 2 3 4
would equate to 1+1+1+1=4

Eg. 1 2 1

would equate to 3+1=4   (since 1 occurs twice , n(n+1)/2=3)

Now the input can range from -1000001 and 1000001.

My original method of doing this caused me to time out, even though I was coding it in python.

I finally found a way to organize my data. I simply hashed the numbers present in the input into 2 arrays, one for positive numbers and another for negative numbers.

Then I simply ordered them in ascending order (I'll explain the benefits of arranging your numbers in a sorted order and then working on it in another blog post. But apparently, it can improve the running time up to 6 times!)

Every time a number occurs, I simply incremented the occurrence since my array/list was initialized to 0 for every item.

If 2 occurred thrice then list[2]++ would occur thrice causing its value to be 3

Then I ran a for loop, and checked if the occurrence was greater than 0. If so, I applied the formula and kept adding.

If you have any doubts let me know.




def read():
isum=0
fisum=0
freq=0
lex=[0]*1000001
lexneg=[0]*1000001
s=raw_input("")
numbers = map(int, s.split())
for y in numbers:
if(y>=0):
lex[y]+=1
else:
y=abs(y)
lexneg[y]+=1
for y in xrange(0,1000001):
if(lex[y]>0):
isum=(lex[y]*(lex[y]+1))/2
fisum=fisum+isum
if(lexneg[y]>0):
isum=(lexneg[y]*(lexneg[y]+1))/2
fisum=fisum+isum

print fisum


n=raw_input("")
n=int(n)
for z in xrange(0,n):
x=raw_input("")
read()