This question was already discussed.
On 14 October 2010 15:36, Manish K <[email protected]> wrote:
> 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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Thanks and Regards,
N. Ravikanth
--
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.
