Given an array find any two numbers with sum equal to rest of sum
Answers
Ideally you should think a solution all yourself before asking this question, assuming you did I am writing below.
Sure, I forgot most of what I learnt in algorithms by now, but since you asked only algorithm, which is the right way, I will try the raw one without seeing the link since it looks to be new one for me.
A is array. Say N is the number of elements.
x is number which is sum of some 2 numbers in array.
if I deduct x from A[N-1] (last ele), call it as diff, and then find if the diff is in A[0, N-2], then it should tell if that pair (A[N-1], diff) exists.
If not found, continue with A[N-2] (last second ele), till array has single element.
Since you are searching all the array (N), and if find the diff is with binary search (log N), we are seeing N logN
To retry for a bit better logic,
I would consider choosing A[N-1], A[N-2] in non-sequential way, that is, instead of, from last to first, I might take a binary search there as well, that is, i would pick the mid element of array, then mid of left side array of it, or right side array of it. Here i guess the diff will help when it is -ve or +ve to go which side array of mid element.
Once it is possible from previous N * log N, you would improve to log N * log N, which should be faster.
Obviously I see that there may be better solution using more memory here.
In general, when I think of a solution which is less than N log N, like log N * log N now, only then I code to save time.
Hoping above quick raw one helps in an optimal solution for you.