A -> 5, 4, 2, 1 B -> 6, 5, 4, 2, M -> <6,b>,<5,a>,<5,b>,<4,a>,<4,a>,<2,a>,<2,a>,<1,a>
x=6b, find the index of B[1]=5 in A, which is 0. so 1 big number. k=1 x=5a, find the index of A[1]=4 in B, which is 3. so there are 2 more, k=3 . . . In the case if k=2 is asked, we know that k=2 can be found when a=5, then simply find the the first largest pair to get the 3rd. if you find the index by binary search then its logn or logm to search, doing it for n numbers i A takes mlogn, and for B it is nlogm. I hope it helps to get the main idea, there are details I am avoiding. (don't want to waste too much time on this) On Oct 7, 5:07 pm, sourav <[email protected]> wrote: > @Ercan > > I am not clear about your approach. It is clear than you are creating > a single list of numbers which is a merge of numbers from both array > such that final list / array is also decreasing. This can be done in > O(m+n). > > But what after that? Will be great if you can give some more detail. > > Thanks > Sourav > > On Oct 7, 5:30 am, Gönenç Ercan <[email protected]> wrote: > > > > > 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.
