this will not work out
a[0]>b[0] doesn't mean that a[0]+b[i] is ith largest sum
try
int a[]={10,8,6,4,1};
int b[]={9,6,3,2,1};
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Wed, Oct 6, 2010 at 11:36 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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://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 [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.
