Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

hama

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.

  • one year ago
  • one year ago

  • This Question is Closed
  1. agdgdgdgwngo
    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?)

    • one year ago
  2. hama
    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!

    • one year ago
  3. shandelman
    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.

    • one year ago
  4. shandelman
    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...

    • one year ago
  5. shandelman
    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.

    • one year ago
  6. shandelman
    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.)

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

    I'll try that. Thanks!

    • one year ago
    • Attachments:

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