Nice question:
1. |A| = |B| i.e I assume their cardinality is equal
2. A(n) = { a1, a2 a3, ...aN} such that a1>=a2>=a3...>=aN
3. B(n) = { b1, b2 b3, ...bN} such that b1>=b2>=b3...>=bN
4. S(n^2) = A x B = {(a1,b1), (a1,b2)....(a1,bN),
(a2,b1), (a2,b2)....(a2,bN),
....
(aN,b1), (aN,b2)....(aN,bN)}
assuming we have added in a way such that we find a pair ai > bi,
for some i in 1..N such that a(i-1) = b(i-1)
A first observation is that in the worst case, the first 2N numbers in
S will contain the final result of N numbers.
i.e in (a1,b1), (a1,b2)....(a1,bN), (a2,b1), (a2,b2)....(a2,bN)
In the best case first N numbers in S will contain the final N numbers
(already sorted in decreasing order)
i.e in (a1,b1), (a1,b2)....(a1,bN)
Now, if we consider again the worst case scenario, then we can first
divide 2N numbers in two groups of size N each and each of this group
is already sorted in decreasing order.
i.e (a1,b1), (a1,b2)....(a1,bN) and (a2,b1), (a2,b2)....(a2,bN)
Now we can simply apply Merge Algorithm on these 2 already sorted
arrays of size N each in O(N) time, which solves the problem
I can be wrong only if the the results lie outside first 2N
numbers(which I hope is not the case).
On Apr 30, 2:05 pm, divya <sweetdivya....@gmail.com> 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.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group
> athttp://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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
