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.
