Got Homework?
Connect with other students for help. It's a free community.
Here's the question you clicked on:
 0 viewing
hama
Group Title
How can I count the number of pairs that sum to 0 in an unsorted array in linear time? I could have it in order of n log (n) using binary search, but I want to make it even faster than that.
 2 years ago
 2 years ago
hama Group Title
How can I count the number of pairs that sum to 0 in an unsorted array in linear time? I could have it in order of n log (n) using binary search, but I want to make it even faster than that.
 2 years ago
 2 years ago

This Question is Closed

agdgdgdgwngo Group TitleBest ResponseYou've already chosen the best response.0
see if you can make some assumption on the data (are the elements all unique? Are the values of the elements as large as the size of the array?)
 2 years ago

hama Group TitleBest ResponseYou've already chosen the best response.0
They're not necessarily unique and they can be smaller or larger than the size of the array, just random numbers. But I don't see how that makes any difference in the algorithm!
 2 years ago

shandelman Group TitleBest ResponseYou've already chosen the best response.1
I think I've come up with a solution in Python using hash tables (the dictionary type specifically) since lookup time on hash tables is very very fast. Basically, the function walks through the list, and for every number x, it checks if x is in the hash table. If it's not, it adds x to the hash table, and if it is, it increases the count and deletes x from the hashtable. I keep increasing the number of numbers by a factor of ten and the time keeps increasing by a factor of ten, so, yeah...linear.
 2 years ago

shandelman Group TitleBest ResponseYou've already chosen the best response.1
Actually, whoops, this doesn't quite work for inputs such as [5,5,5,5,5,5] because it will just return 1...hmm...
 2 years ago

shandelman Group TitleBest ResponseYou've already chosen the best response.1
Okay, the problem I introduced can easily be fixed by putting the number into the hash table and giving it the value of its count. So, the first time it sees a 5, it will put the key 5 and value 1 into the dictionary, and every other time it sees a 5, it will add 1 to its value. Then, when it sees its counterpart 5, it will decrement 5's value until it reaches zero, where it deletes it from the dictionary. A little flub on my part, but not too bad of a fix.
 2 years ago

shandelman Group TitleBest ResponseYou've already chosen the best response.1
(And this is why we come up with good test cases before tackling a problem, by the way. Heh heh.)
 2 years ago

hama Group TitleBest ResponseYou've already chosen the best response.0
I'll try that. Thanks!
 2 years ago
See more questions >>>
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.