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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.