Quantcast

A community for students. Sign up today!

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

hama

  • 2 years ago

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.

  • This Question is Closed
  1. agdgdgdgwngo
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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. hama
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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!

  3. shandelman
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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.

  4. shandelman
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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...

  5. shandelman
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 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.

  6. shandelman
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    (And this is why we come up with good test cases before tackling a problem, by the way. Heh heh.)

  7. hama
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I'll try that. Thanks!

  8. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Ask a Question
Find more explanations on OpenStudy

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.