I have formulated a solution, not strictly of O(n), but I guess it's close.
=== 1. for(int k=0;k<n;k++) { 2 get_max_of_temp_array(maxVal,visited_index_of_A/*Va[i]*/,visited_index_of_b/*Vb[j]*/); 3. Print_Max_of( a[va[i]+1] +b[Vb[j]] , a[va[i]] + b[vb[j+1]] ,maxVal) 4 insert_other_two_of_the_triplet(); 5 (i,j)=(index_of_maximum_value printed_above); 6 update_Va_&_Vb_accordingly(); } insert... on line 6 is to insert the (set-)element in an insertion-sorted array. But still not O(n). :( On Wed, Jul 28, 2010 at 4:11 PM, manish bhatia <mb_mani...@yahoo.com> wrote: > I guess your solution would also be proved incorrect with the following, > > Numbers in bold are the two arrays. > > 125 122 120 110 104 103 102 101 > 100 99 98 97 > 130 255 252 250 240 234 233 232 231 230 > 229 228 227 > 128 253 250 248 238 232 231 230 229 228 > 227 226 225 > 126 251 248 246 236 230 229 228 227 226 > 225 224 223 > 125 250 247 245 235 229 228 227 226 225 > 224 223 222 > 105 230 227 225 215 209 208 207 206 205 > 204 203 202 > 104 229 226 224 214 208 207 206 205 204 > 203 202 201 > 103 228 225 223 213 207 206 205 204 203 > 202 201 200 > 102 227 224 222 212 206 205 204 203 202 > 201 200 199 > 101 226 223 221 211 205 204 203 202 201 > 200 199 198 > 100 225 222 220 210 204 203 202 201 200 > 199 198 197 > 99 224 221 219 209 203 202 201 200 > 199 198 197 196 > 98 224 221 219 209 203 202 201 200 > 199 198 197 196 > > > manish... > > > ------------------------------ > *From:* Varun Nagpal <varun.nagp...@gmail.com> > *To:* Algorithm Geeks <algogeeks@googlegroups.com> > *Sent:* Mon, 3 May, 2010 12:26:24 PM > *Subject:* Re: [algogeeks] Re: a google question > > 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 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. > > > -- > 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.