My previous post went unfinished :(( anyway this is summary of algo . (as N is very large , sorting could be costly so this method doesn't do that )
algo :: have a map<int,bool> 1. For given number , if its less than Sum S , make map[S-number] = true only if map[number] does not exist 2. for Next number , if map[number] is true , we got a pair ( number , map[number]) else do 1 For exampe S = 100 , if we get 20 , let's make map[80] = true ; next if we get 80 , we will first check map[80] and if its true , we get a pair. If there are repetations , we can take map of <int,int> where second argument is count of first element , say of 20 comes 4 times we will store map[20] = 4 On Jun 12, 11:40 am, Chakravarthi Muppalla <[email protected]> wrote: > I would use an array. > > a[] = 1 3 7 8 9 78 67 23 > a[] = 1 3 7 8 9 23 67 78 //sort the array > reqSum = 30; > for i :a.length-1; i>=0; i-- > t = reqSum - a[i]; > if(t is negative) continue; > find(t);//in the rest of the array;(binary search) > if(t found in the array) return index of t, current value of i; > I guess it works.(we may have to use a hash map to speed it up in the long > run). > > On Sat, Jun 12, 2010 at 10:29 AM, Rohit Saraf > <[email protected]>wrote: > > > > > I guess it can be done in efficiently using a simple divide and conquer > > scheme almost imitating mergesort. > > Can you think of it now? :D > > > -------------------------------------------------- > > Rohit Saraf > > Second Year Undergraduate, > > Dept. of Computer Science and Engineering > > IIT Bombay > >http://www.cse.iitb.ac.in/~rohitfeb14 > > > On Fri, Jun 11, 2010 at 10:07 PM, sharad kumar > > <[email protected]>wrote: > > >> all possible pairs > > >> -- > >> 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]<algogeeks%[email protected]> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Thanks, > Chakravarthi. -- 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.
