merge the A and B in a queue in sorted order. find the following number (next in original array a_i+1) of the largest number (next in queue a_i) execute binary search in the other array (B), the index returned from binary search (even if its not in the array) gives the number of sums greater than the next greatest in A, a_i+1. so; we know the number of pairs;
(a_i , b_j) where b_j > a_i+1 if you know one of the numbers then the other can be found easily. I think this is O(nlogm + mlogn) On Oct 7, 2:16 am, Gönenç Ercan <[email protected]> wrote: > A -> 5, 4, 2, 1 > B -> 6, 5, 4, 2, 1 > > k = 3, > > ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the > algorithm below give 8 (a=2, b=6)? > > On Oct 6, 9:06 pm, ligerdave <[email protected]> wrote: > > > > > use pointers and lengths of two arrays. depends on what K is, if K> > > m*n/2, you reverse the pointers. therefore, the worst case is either > > O(m) when length of m is shorter or O(n) when length of n is > > shorter, > > > make the pointers pointing to the first elements in both arrays. > > > A) > > 4,3,2,2,1 > > ^ > > > B) > > 5,3,2,1 > > ^ > > > compare them to find out which one is larger, here 5 is larger than 4. > > by definition, you know 5 would be bigger than any elements in array > > A, and sum of 5 with kth element of array A (here, kth <= A.length) > > will be the one(kth largest sum(a+b) overall) you are looking for. > > > if k>A.length, shift the pointer of B one number to the right and > > repeat the same process. > > > like i said, if the k> m*n/2, start from small > > > On Oct 6, 6:34 am, sourav <[email protected]> wrote: > > > > 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. thnkx in advance. -- 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.
