Timeline for The most efficient algorithm to find all possible integer pairs which sum to a given integer
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 27, 2019 at 23:15 | comment | added | Daniel Lichtblau |
Assuming the hashing and lookup are O(1), an O(n) method is as follows. (1) Hash all values in the list. (2) Iterate over the list, checking for each value k whether m-k was hashed. Can use Sow to record the pair, and Reap to gather all pairs sown.
|
|
| Mar 26, 2019 at 10:07 | answer | added | Simon Erni | timeline score: 3 | |
| Mar 26, 2019 at 3:00 | history | tweeted | twitter.com/StackMma/status/1110376062448558080 | ||
| Mar 25, 2019 at 21:58 | comment | added | Christopher Mowla | According to my knowledge, I did need to use some type of sort for my algorithm. However, I clearly see now (by Roman's post) that my algorithm isn't the most efficient out there. So I guess I'm not worried about it anymore. I wrote this algorithm as part as my coding challenge for a position at Wolfram Research about four months ago. I was just curious if someone could identify what I did or if it is a new way to approach this old classic problem. Thanks, guys! | |
| Mar 25, 2019 at 21:48 | vote | accept | Christopher Mowla | ||
| Mar 25, 2019 at 19:36 | history | became hot network question | |||
| Mar 25, 2019 at 18:37 | comment | added | MikeY |
You have a Sort call. Use SortBy instead, it is much faster than Sort. But you probably don't need to sort it anyway.
|
|
| Mar 25, 2019 at 18:10 | answer | added | Roman | timeline score: 16 | |
| Mar 25, 2019 at 18:04 | comment | added | Henrik Schumacher |
The presence of an Append indicates that the complexity of the algorithm is larger than you expect...
|
|
| Mar 25, 2019 at 18:04 | history | edited | Henrik Schumacher |
edited tags
|
|
| Mar 25, 2019 at 17:52 | history | edited | Christopher Mowla | CC BY-SA 4.0 |
deleted 3 characters in body
|
| Mar 25, 2019 at 17:50 | review | First posts | |||
| Mar 25, 2019 at 18:31 | |||||
| Mar 25, 2019 at 17:45 | history | asked | Christopher Mowla | CC BY-SA 4.0 |