@lingerdave If you get the larget element from the 2 arrays A -> 5, 4, 2, 1 B -> 6, 5, 4, 2,
say 6, do not underestimate the next element in A. The difference between the first two elements in A may be less and 2nd element in A may be string enough to make itself plus an element in B greater than first element in A plus kth element in B. More so if elements in B are very small after first few. for example see example A-> 100, 99, B-> 50,9,2,1,1 Here A[i] + B[1} is largest but A[2]+B[1] is much larger than A[2]+B[2]. Sourav On Oct 7, 6:22 pm, ligerdave <david.c...@gmail.com> wrote: > @ Ercan, > > yes, you were right. i forgot about that. > anyway, that's the idea. you would need to move pointers on both, > depends on which is bigger. for loop w/ i<=k, when the loop stops, you > have the pointers pointing at the numbers you wanted > > On Oct 6, 7:16 pm, Gönenç Ercan <gon...@gmail.com> 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 <david.c...@gmail.com> 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 <souravs...@gmail.com> 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 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.
