Correction:
On Thu, Oct 7, 2010 at 11:12 AM, sumant hegde wrote:
> If S(h)= a[p]+b[q] and S(i)= a[r]+b[s], then obviously p >= r and q>= s,
>
.. then p >= r and q <= s..
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this grou
Let S(k) indicate the kth largest sum as per the question. We can also say
that every S corresponds to a pair, (u,v) such that S=a[u]+b[v].
Now the idea is to keep track of two previous S's (in turn two pairs) such
that one pair has the greatest 'u' of all so-far pairs. That is, this pair
has most
you are given 2 arrays sorted in decreasing order of size m and n
respectively.
Input: a number k <= m*n and >= 1
Output: the kth largest sum(a+b) possible. where
a (any element from array 1)
b (any element from array 2)
The Brute force approach will take O(n*n). can anyone find a better
logic.
