Little problem(s) July 2022

[John Keith]

(07-05-2022 09:41 PM)Albert Chan Wrote:  BTW, if the list were sorted, there is no need for POS at all.
We just repeatedly shorten the 2 tails ...

Code:

function f2(lst, x) -- lst sorted, no duplicates
    local i, j = 1, #lst
    while i < j do
        local y = lst[i] + lst[j] - x
        if     y > 0 then j=j-1
        elseif y < 0 then i=i+1
        else print(i, j); i=i+1; j=j-1
        end
    end
end

lua> f2({2,7,11,15}, 17)
1      4
lua> f2({2,5,7,8,10,11,15}, 15)
2      5
3      4

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.