i think ,you can use the idea of merg (merg sort) --- On Mon, 7/19/10, manish bhatia <[email protected]> wrote:
From: manish bhatia <[email protected]> Subject: Re: [algogeeks] a google question To: [email protected] Date: Monday, July 19, 2010, 5:03 PM 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. manish... From: Ashish Goel <[email protected]> To: [email protected] Sent: Sun, 18 July, 2010 6:31:08 PM Subject: Re: [algogeeks] a google question question please... Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Fri, Jul 16, 2010 at 4:43 PM, manish bhatia <[email protected]> wrote: It doesn't work.... A => 92 87 81 72 70 61 53 22 18 17 B => 79 78 74 68 64 62 57 34 29 24 C (GOLD) => 171 170 166 166 165 161 160 160 159 156 D (TEST) => 171 170 166 166 165 159 155 155 146 145 Result: FAILED! manish... From: Jitendra Kushwaha <[email protected]> To: [email protected] Sent: Sun, 2 May, 2010 9:13:14 PM Subject: Re: [algogeeks] a google question Here is a solution of O(n) , taking 4 pointers 2 for each array #include <cstdio> #include<iostream> using namespace std; #define N 10 int main(void) { int arr1[N] = {8,7,4,3,2,1,1,1,1,1}; int arr2[N] = {34,23,21,19,15,13,11,8,4,2}; int *p11,*p12,*p21,*p22; p11 = p12 = arr1; p21 = p22 = arr2; int f1; f1 = 0; for(int i=0;i<N;i++) { int ans=0; int a,b,c,d; a = *p11 + *p21; b = *p11 + *p22; c = *p21 + *p12; d = *(p11+1) + *(p21+1); //printf("a=%d b=%d c=%d d=%d\n",a,b,c,d); //debug if(f1==0) ans = a , p12++ , p22++ , f1=1; else if(b >= c && b >= d ) ans = b , p22++ ; else if(c >= b && c >= d ) ans = c , p12++ ; else ans = d , p11++ , p21++ ,printf("4 "); printf("%d\n",ans); } } Regards Jitendra Kushwaha Undergradute Student Computer Science & Eng. 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 [email protected]. To unsubscribe from this group, send email to [email protected]. 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 [email protected]. To unsubscribe from this group, send email to [email protected]. 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 [email protected]. To unsubscribe from this group, send email to [email protected]. 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 [email protected]. To unsubscribe from this group, send email to [email protected]. 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
