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.
Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga.
Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus.
Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
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?)
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!
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.
Not the answer you are looking for? Search for more explanations.
Actually, whoops, this doesn't quite work for inputs such as [-5,-5,-5,5,5,5] because it will just return 1...hmm...
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.
(And this is why we come up with good test cases before tackling a problem, by the way. Heh heh.)