Hi,
Take an example :
Array A: {a1,a2,a3,a4,a5}- (sorted decreasingly)
Array B :{b1,b2,b3,b4,b5}- (sorted decreasingly)
First pair is(a1,b1) .
Now for Second pair Compare the sum of (b1,a2) and (a1,b2) whichever is
greater .
if (a1,b2) is the second pair then now compare (b1,a2) and (a1,b3) .
Repeat the above process till u will get first n pairs.
Complexity O(n).
Thanks
Manish
On Thu, Oct 14, 2010 at 3:24 PM, arun raghavendar <[email protected]>wrote:
> 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]<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.
