use map<int,bool> S when you encounter a particular number check S[x-num] is true, if so return that pair. else S[num]=true
On Sat, Sep 11, 2010 at 1:09 PM, topojoy biswas <topojoy.bis...@gmail.com>wrote: > 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<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 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.
