Better than O(n):
start = 0;
end = n-1;
Loop
{
take a[start] and search for a number equal to or just less than x -
a[start] in array between a[start] and a[end]
If x - a[start] is found, break;
else
Lets this number be at position p. Set end = p
Now, take a[end] and search for a number equal to or just larger than
x-a[end] in array between a[start] and a[end].
If x - a[end] is found, break;
else
Let this number be at position p. Set start = p;
}(until start<=end)
For searching the number, use binary search.
Enjoy..
On Sun, Oct 10, 2010 at 6:59 PM, ashish agarwal <
[email protected]> wrote:
> take two pointer p and q
> p=a[0] and q=a[n-1];
> sum=p+q;
> if(sum>x)
> q--;
> if (sum<x)
> p++;
>
>
>
>
> On Sun, Oct 10, 2010 at 6:54 PM, Rohit <[email protected]> wrote:
>
>>
>>
>> On Oct 10, 10:48 am, Shravan <[email protected]> wrote:
>> > http://ideone.com/D5W2y
>> >
>>
>> Good :).
>> What if array is unsorted. What will be the best solution in terms of
>> time complexity?
>> Better then (nlog(n)+n).
>>
>> Regards
>> Rohit
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Saurabh Gupta
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
