Author |
Topic: Find first k smallest sum of two sorted array (Read 8413 times) |
|
colorwinds
Newbie
Posts: 8
|
 |
Find first k smallest sum of two sorted array
« on: Oct 30th, 2008, 6:29pm » |
 Quote  Modify
|
Let A and B are sorted array with length m and n respectively, given k, the problem is to find the first k smallest elements which are composed of A[i]+B[j].
e.g.
A={1,3,5,7}, B={2,6, 10}, k = 3
Output:
1+2
3+2
1+6
Thanks!
|
|
 IP Logged |
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Find first k smallest sum of two sorted array
« Reply #1 on: Oct 30th, 2008, 11:12pm » |
Quote Modify
|
I think it can be solved in a similar way we solve for finding minimum spanning tree using Prims algorithm
Find k such minimum edges
|
| « Last Edit: Oct 30th, 2008, 11:14pm by howard roark » |
IP Logged |
|
|
|
nks
Junior Member
Gender: 
Posts: 145
|
|
Re: Find first k smallest sum of two sorted array
« Reply #2 on: Oct 31st, 2008, 12:09am » |
Quote Modify
|
Please correct me in output of example
Answer will be only 1+2 =3
what do u mean by find the first k here ?
|
|
IP Logged |
|
|
|
colorwinds
Newbie
Posts: 8
|
|
Re: Find first k smallest sum of two sorted array
« Reply #3 on: Oct 31st, 2008, 12:19am » |
Quote Modify
|
for C[1: m*n], where C[k]= A[i]+B[j]
C is in ascending order
if k==3, I want to find C[1:k] and its corresponding A[i] and B[j].
Time complexity requirement is O(k).
|
|
IP Logged |
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Find first k smallest sum of two sorted array
« Reply #4 on: Oct 31st, 2008, 12:46am » |
Quote Modify
|
I dont know if it is possible in O(k) time... but it is very simple to do it in O(klogk)
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find first k smallest sum of two sorted array
« Reply #6 on: Oct 31st, 2008, 7:50am » |
Quote Modify
|
I would divide the problem into 3 easier ones:
1) Find the k-th sum value v
2) Write all sums less than v and make a list of sums equal to v (while the result len + list len < k only!).
3) Write required number of sums from the list.
The goal is not well defined ... according the definition may be 3) and 2) can be unioned together.
2) Is simple: For values from A array in increasing order list all B elements (in increasing order) such that the condition for the sum holds. Stop when for the value there were no progress (even the list was not extended).
3) Depends on the goal, but should be simple 
So how to do 1) efficiently?
|
| « Last Edit: Oct 31st, 2008, 7:52am by Hippo » |
IP Logged |
|
|
|
dav
Newbie
Gender:
Posts: 47
|
|
Re: Find first k smallest sum of two sorted array
« Reply #7 on: Feb 13th, 2009, 7:31am » |
Quote Modify
|
Iam still not getting the soln for this. any better soln please
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find first k smallest sum of two sorted array
« Reply #8 on: Feb 16th, 2009, 1:03pm » |
Quote Modify
|
For 1) we are looking for k-th sum v.
Let A contains n elements as well as B.
O(n) is sufficient to test how many sums are greater than given sum s and how many are less.
We can partition sums into 5 categories:
Less than already tested pivot smaller than v (S-2 ), less than current pivot
(S-1), equal to current pivot (S0), bigger than current pivot (S1),
bigger to already tested pivot greater than v (S2).
Let their sizes be s-2,s-1,s0,s1, and s2.
If s-2+s-1  k, "move" S0 and S1 to S2 and
choose new pivot in S-1.
If s-2+s-1+s0  k, "move" S0, S-1 to
S-2 and choose new pivot in S1.
Both s-2 and s2 are incremented and elements moved to S-2 and
S2 are never more considered.
We actually neednot evaluate all elements of S , only their sizes are important.
We can for each A[i] maintain sizes a[i]j of A[i]+B[x] Sj.
We can maintain double linked list of a[i]'s and remove a[i] from the list whenever
a[i]-2+a[i]2=n.
So how to choose the pivot most efficiently?
Choose median sum A[i]+B[x] for each A[i] with a[i]-1+a[i]0+a[i]1 3. Let pivot be median of these medians weighted by sizes a[i]-1+a[i]0+a[i]1.
When a[i]-1+a[i]0+a[i]1 2 for each i, let pivot be median of all values in S-1 S0S1.
In all cases pivot was choosen in O(n) time and roughly at least one fourth of the sums is discarded using the pivot in time O(n). So after is O(\log n) steps the k-th sum is find. Overall time would be O(n\log n).
The only open question is how to find weighted median efficiently.
|
| « Last Edit: Feb 16th, 2009, 1:06pm by Hippo » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find first k smallest sum of two sorted array
« Reply #9 on: Feb 16th, 2009, 2:05pm » |
Quote Modify
|
Why not use a min-heap of pairs (ik,jk), using ordering on A[ik] + B[jk]
Initialize the heap with pairs (ik=k, jk=0) for k=0..n-1
On removing (ix,jx), replace it with (ix,jx+1)
It gives you all the smallest sums, in order, in O(k log(n)) time. As mentioned/referred to by VincentLascaux.
Why complicate things for a worse result?
|
| « Last Edit: Feb 16th, 2009, 2:44pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find first k smallest sum of two sorted array
« Reply #10 on: Feb 17th, 2009, 1:40pm » |
Quote Modify
|
on Feb 16th, 2009, 2:05pm, towr wrote:Why not use a min-heap of pairs (ik,jk), using ordering on A[ik] + B[jk]
Initialize the heap with pairs (ik=k, jk=0) for k=0..n-1
On removing (ix,jx), replace it with (ix,jx+1)
It gives you all the smallest sums, in order, in O(k log(n)) time. As mentioned/referred to by VincentLascaux.
Why complicate things for a worse result? |
|
If k O(n) there is no need for complication, but if k,n2-k (n2). So I don't thing it's worse result
BTW: If n (size of A) is less or equal to m (size of B), I would use the algorithm as described, otherwise I would swap A with B.
|
| « Last Edit: Feb 17th, 2009, 1:43pm by Hippo » |
IP Logged |
|
|
|
dav
Newbie
Gender:
Posts: 47
|
|
Re: Find first k smallest sum of two sorted array
« Reply #11 on: Feb 17th, 2009, 8:38pm » |
Quote Modify
|
towr,
what if the k is large. it is almost equal to n. Doesnot performance wonot go down ?
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find first k smallest sum of two sorted array
« Reply #12 on: Feb 17th, 2009, 10:29pm » |
Quote Modify
|
on Feb 17th, 2009, 8:38pm, dav wrote:towr,
what if the k is large. it is almost equal to n. Doesnot performance wonot go down ? |
|
k=n is small enough, k=n2/2 is problem.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find first k smallest sum of two sorted array
« Reply #13 on: May 5th, 2009, 6:55am » |
Quote Modify
|
I have looked for finding n-th element of sum of two n-element sorted arrays.
... with no success. This was one of topics when James Fingas written.
[edit]Oh yes That was it[/edit]
Now while searching for it I have found the linear weighted median was discussed by him, too.
... weighted median can easily be found by pivoting against nonweighted median. This leads to linear algorithm even for weighted median. This can be speeded up by factor around 2 by pivoting against nonweighted median of nonweighted medians of five element groups (this approximation of nonweighted median is good enough).
The trick for n-th element in sum of two sorted arrays was in dividing the implicit square matrix according the main diagonal and maintain subrows in upright part and subcolumns in leftdown part. Testing corresponding pivot can be speeded up by binary search in each part (If the number of subrows+subcolumns is o(n/log n) ... for k resp. (n2-k) in o((n/log n)2)).
Choosing new pivot as weighted median of subrows+subcols leads to discarding 1/4 of sum candidates each round. Leading to total time O(min(n,(\sqrt min(k,n2-k))log n)*log n).
|
| « Last Edit: Jun 13th, 2009, 3:33pm by Hippo » |
IP Logged |
|
|
|
cryptogrammer
Newbie
Posts: 3
|
|
Re: Find first k smallest sum of two sorted array
« Reply #14 on: Jun 11th, 2009, 6:25am » |
Quote Modify
|
Hippo can u plz explain ur alorithm by giving an exmaple.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Find first k smallest sum of two sorted array
« Reply #15 on: Jun 13th, 2009, 3:53pm » |
Quote Modify
|
I am too lazy to made an example. But the algorithm is exactly the same James Fingas hinted (k n does not change it's principle).
|
| « Last Edit: Jun 13th, 2009, 3:55pm by Hippo » |
IP Logged |
|
|
|
ONS
Newbie
Gender:
Posts: 41
|
|
Re: Find first k smallest sum of two sorted array
« Reply #16 on: Jun 16th, 2009, 2:27am » |
Quote Modify
|
this sol runs in O(k) time....
#include<stdio.h>
#define MAXSIZE 10
int main(void)
{
int a[MAXSIZE]={1,5,7,9,12,26,33,45,56,58};
int b[MAXSIZE]={2,3,5,8,14,16,20,22,25,50};
int i=1,j=1,k;
int reqNum;
printf("Enter the no. of sums required: ");
scanf("%d",&reqNum);
if(reqNum>0)
{
printf("%d ",a[0]+b[0]);
for(k=2;k<=reqNum;k++)
{
if((a[i]+b[0])<=(a[0]+b[j]))
{
printf("%d ",a[i]+b[0]);
i++;
}
else
{
printf("%d ",a[0]+b[j]);
j++;
}
if(i>=MAXSIZE || j>=MAXSIZE)
{
printf("\noverflow!! all nos. cant be printed!!\naborting\n");
break;
}
}
}
system("pause");
return 0;
}
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find first k smallest sum of two sorted array
« Reply #17 on: Jun 16th, 2009, 3:18am » |
Quote Modify
|
on Jun 16th, 2009, 2:27am, ONS wrote:| this sol runs in O(k) time.... |
|
It runs in O(k), but it isn't a solution. It is not necessarily the case that either a[0] or b[0] is part of the smallest sum.
See also: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1132204952;start=50#59
Also, k may be anything up to n*m, your algorithm can't go further than n+m-1.
|
| « Last Edit: Jun 16th, 2009, 3:37am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ONS
Newbie
Gender:
Posts: 41
|
|
Re: Find first k smallest sum of two sorted array
« Reply #18 on: Jun 16th, 2009, 5:03am » |
Quote Modify
|
Quote: It is not necessarily the case that either a[0] or b[0] is part of the smallest sum.
Also, k may be anything up to n*m, your algorithm can't go further than n+m-1. |
|
oops! i took first statement for granted and messed up with the problem.
thanks for pointing it out
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print