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 <[email protected]> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[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.
