mkagenius
BAN USERMay be there can't be any such solution, with less than O(n) worst case complexity.
Lets see...
suppose someone proposes an algo. which does this in sublinear time, that means
that algorithm will not look at every element, and it is theoretically possible to put those two elements at those positions which is not looked by that algorithm.
Hence looking at every element is necessary in worst case. So we need O(n) time.
But there is a catch, since the array is ordered, there may be a algorithm which does not literally looks at every element but takes advantage of this information about ordering of elements, And thus i think it may be possible to have such algorithm. Although I am not sure.
What I tried ,
take first element of the array, call it "x", now binary search for largest element less equal than (Sum - x). if the sum of those elements is Sum, then we have the answer.
Otherwise, Take second element of array. call it "y", now binary search (Sum - y) in the new limited range. But i guess the time complexity is not better than O(n).
Thanks.
What was your approach ?
My approach :
Time : O(n^3) .
- mkagenius April 11, 2012