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 <[email protected]>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 <[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]<algogeeks%[email protected]> > . > 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 [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.
