Sort the numbers in Set S having n integers. O(nlogn).
Take two variables a and b pointing to least and max index of n.
Move the pointers in such a way that
if(*a+*b > x&&a<=b)
b--;
else if(*a+*b<x&&a<=b)
a++;
else
printf("A&B is found %d + %d = %d",*a,*b,x);
Note this covers the array from two sides and hence summing up to order n.
So total order is O(nlogn)
Since this is covering the array from left and right
On Sat, Sep 10, 2011 at 12:01 PM, Rashmi Jain <[email protected]>wrote:
> given a set of S of n integers and another integer x,determine whether or
> not there exists two elements in S whose sum is exactly x..running time
> should be (n lgn)
>
> --
> *****
> RASHMI JAIN
> 3rd Year,B.E.(IT)
> Delhi technological University
>
> *
>
> --
> 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.
>
--
Thanks and Regards,
Shiwakant Bharti
--
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.
