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 <jagadish1...@gmail.com> 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 <shashank7andr...@gmail.com> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
