Guys no one commented on my solution? Any takes on it?
Anyways, below is my solution (in pseudo code) Pre-condition: A and B are sequences of equal length and sorted in descending order Input: Sequences A[1..N] and B[1..N] of equal lengths(N) Ouput: Sequence C[1..N] containing sorted sum of ordered pairs from cartesian products of A, B or B,A Sort(A,B) { k = 1 N = length(A) = length(B) C[1..2*N] = [] // Empty array cart_prod_order = 0 // 0 -> AxB, 1 -> BxA. 0 is default // Complexity : O(N) while(k != N+1) { if (A[k] < B [k]) { cart_prod_order = 1 break } else { k = k + 1 } } // Choose the correct order of Cartesian product sum // Complexity: Theta(2N) = O(N) if (cart_prod_order == 1) { // take cartesian product of B and A, storing the sum of ordered pair (b,a) in each element of C C[1..2N] = B[1..2] x A[1..N] } else { // take cartesian product of A and B, storing the sum of ordered pair (a,b) in each element of C C[1..2N] = A[1..2] x B[1..N] } // Merge // C[1..N] and C[N+1..2N] are already sorted in descending order // Complexity: Theta(N) C[1..2N] = Merge(C[1..N],C[N+1..2N]) return C[1..N] } Merge(C,D) { i=1,j=1,k=1 E = [] while(i<=length(C) OR j<=length(D)) { if(i<=length(C) AND (j>length(D) OR C[i]>D[j])) { E[k] = C[i] i = i + 1 } else { E[k] = D[j] j = j + 1 } k = k + 1 } return E; } On Fri, Apr 30, 2010 at 7:50 PM, banu <varun.nagp...@gmail.com> wrote: > Nice question: > > 1. |A| = |B| i.e I assume their cardinality is equal > > 2. A(n) = { a1, a2 a3, ...aN} such that a1>=a2>=a3...>=aN > 3. B(n) = { b1, b2 b3, ...bN} such that b1>=b2>=b3...>=bN > > 4. S(n^2) = A x B = {(a1,b1), (a1,b2)....(a1,bN), > (a2,b1), (a2,b2)....(a2,bN), > .... > (aN,b1), (aN,b2)....(aN,bN)} > > assuming we have added in a way such that we find a pair ai > bi, > for some i in 1..N such that a(i-1) = b(i-1) > > A first observation is that in the worst case, the first 2N numbers in > S will contain the final result of N numbers. > i.e in (a1,b1), (a1,b2)....(a1,bN), (a2,b1), (a2,b2)....(a2,bN) > > In the best case first N numbers in S will contain the final N numbers > (already sorted in decreasing order) > i.e in (a1,b1), (a1,b2)....(a1,bN) > > Now, if we consider again the worst case scenario, then we can first > divide 2N numbers in two groups of size N each and each of this group > is already sorted in decreasing order. > i.e (a1,b1), (a1,b2)....(a1,bN) and (a2,b1), (a2,b2)....(a2,bN) > > Now we can simply apply Merge Algorithm on these 2 already sorted > arrays of size N each in O(N) time, which solves the problem > > I can be wrong only if the the results lie outside first 2N > numbers(which I hope is not the case). > > > On Apr 30, 2:05 pm, divya <sweetdivya....@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. >> >> -- >> 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 >> athttp://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.