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
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 xa=b)
b--;
else if(*a+*bxa=b)
a++;
else
printf(AB is found %d + %d = %d,*a,*b,x);
Note this covers the array from two
@rashmi..
just sort the set in O(nlogn)
then use two pointers ... one from first end and another from second
endgiven below...in O(n)..
i=0;
j=n-1;
while(ij)
{
if((a[i]+a[j])==x)
{ printf(%d%d,a[i],a[j]);
break;}
if((a[i]+a[j])x)
j--;
else
i++;
}
do it