Hi, Take an example :
Array A: {a1,a2,a3,a4,a5}- (sorted decreasingly) Array B :{b1,b2,b3,b4,b5}- (sorted decreasingly) First pair is(a1,b1) . Now for Second pair Compare the sum of (b1,a2) and (a1,b2) whichever is greater . if (a1,b2) is the second pair then now compare (b1,a2) and (a1,b3) . Repeat the above process till u will get first n pairs. Complexity O(n). Thanks Manish On Thu, Oct 14, 2010 at 3:24 PM, arun raghavendar <arun.s...@gmail.com>wrote: > Start merging A and B from the tail end for N elements, just like the way > you would do it for a merge sort but with a different constraint based on > the sum a[i] and b[i] > > This should work for any value of N, I just hard-coded it for simplicity. > > > #include<stdio.h> > #define N 6 > struct OutputType { > int a; > int b; > int value; > }; > > int main() { > int a[N] = {1,8,13,24,25,30}; > int b[N] = {5,6,17,28,29,29}; > struct OutputType s[N]; > int i, a_candidate_1 = N-1, a_candidate_2=N-2, b_candidate_1=N-1, > b_candidate_2=N-2; > s[0].a = a[N-1]; > s[0].b = b[N-1]; > s[0].value = a[N-1] + b[N-1]; > for (i=1;i<N;i++) { > if ((a[a_candidate_1]+b[b_candidate_2]) >= > (a[a_candidate_2]+b[b_candidate_1])) { > s[i].a = a[a_candidate_1]; > s[i].b = b[b_candidate_2]; > s[i].value = a[a_candidate_1]+b[b_candidate_2]; > b_candidate_2--; > if (b_candidate_2 < 0) { a_candidate_1--; } > } else { > s[i].a = a[a_candidate_2]; > s[i].b = b[b_candidate_1]; > s[i].value = a[a_candidate_2]+b[b_candidate_1]; > a_candidate_2--; > if (a_candidate_2 < 0) { b_candidate_1--; } > } > } > > for (i=0;i<N;i++) printf("(%d,%d)=>%3d ", s[i].a, s[i].b, > s[i].value); > > return 0; > } > > > -Arun > > > On Thu, Oct 14, 2010 at 1:25 PM, Harshal <hc4...@gmail.com> wrote: > >> >> Given two sorted postive integer arrays A[n] and B[n] (W.L.O.G, let's >> >> >> say they are decreasingly sorted), we define a set S = {(a,b) | a \in A >> and b \in B}. Obviously there are n^2 elements in S. The value of such >> a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs >> >> >> from S with largest values. The tricky part is that we need an O(n) >> algorithm. >> >> >> -- >> Harshal Choudhary, >> III Year B.Tech Undergraduate, >> Computer Engineering Department, >> National Institute of Technology Surathkal, Karnataka >> India. >> >> -- >> 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<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.