put all the numbers in a hash table( which demands O(n) space) and then pick each number in the array and check in the hashtable whether x-chosen number is present. this would take O(1) per search. Do it for all the numbers in the array. It wold take O(n).
On Fri, Sep 10, 2010 at 11:00 PM, jagadish <[email protected]> wrote: > Hi, > O(n) solution is possible if the array is presorted! > Else i think it is NOT. > 1.Have two ptrs (one from first and other to track the array from > last) > 2.s=a[left]+a[right] > 3.if(s<sum) left++; > else if(s>sum) right--; > else > print "sum found" > > On Sep 10, 10:19 pm, bittu <[email protected]> wrote: > > Q Given an array, find out if there exists a pair of nos. that adds up > > to a sum 'x' > > > > in O(n) ???? possible,, > > -- > 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. > > -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- 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.
