Re: [algogeeks] sum to x
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 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 > 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 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. >> > > -- > 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. > -- 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 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.
Re: [algogeeks] sum to x
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 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 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. > -- 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.
Re: [algogeeks] sum to x
trivial solution will be exponential where we check for each selection nC1+nC2...nCn = 2^n we can optimise time by taking some memory. It can be solved by subset sum where we will require extra memory of maximum sum possible. refer this link for subset sum problem: http://en.wikipedia.org/wiki/Subset_sum_problem -- Regards Jitendra Kushwaha MNNIT, Allahabad -- 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.
Re: [algogeeks] sum to x
I think we can use a Linked List. Sort it and then find numbers adding upto x. On Fri, Jun 11, 2010 at 9:39 PM, Raj N wrote: > @sharad: Does it have to return the first pair or all possible pairs ? > > > On Fri, Jun 11, 2010 at 6:56 PM, sharad wrote: > >> Given a large file, having N (N is very large) positive integers, how >> will you find a pair of numbers that add up to x (eg. 100). What data >> structure will you use and give appropriate Algo/code. It should be >> efficient in time and space. >> >> -- >> 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. >> >> > -- > 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. > -- 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.
Re: [algogeeks] sum to x
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 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.
Re: [algogeeks] sum to x
@sharad: Does it have to return the first pair or all possible pairs ? On Fri, Jun 11, 2010 at 6:56 PM, sharad wrote: > Given a large file, having N (N is very large) positive integers, how > will you find a pair of numbers that add up to x (eg. 100). What data > structure will you use and give appropriate Algo/code. It should be > efficient in time and space. > > -- > 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. > > -- 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.
