Little problem(s) July 2022

[Albert Chan]

(07-06-2022 01:29 PM)John Keith Wrote:  This is a very good solution, especially for languages that have sets or binary trees as data types.
On the HP48, unfortunately, a UserRPL implementation would be slower than one using POS.

Solution only need O(1) array lookup, not "weird" data types.

With numbers sorted, if two ends add up to required sum, we find the pair.
If more than required sum, throw away the big one.
If less, throw away the small one.

Rinse and repeat, we can find a pair (or, all of them!), with required sum, in O(n)

Of course, depending on list size, worse algorithm may be faster.
Hybrid sorting algorithms switch over algorithms, depending on data, to gain efficiency.