n largest sum
5 posters
Page 1 of 1
n largest sum
two arrays of length n (decreasingly sorted) .now take an element from the first array and another from the second and add them both ....
the aim is to find such n largest sums in o(n) complexity
the aim is to find such n largest sums in o(n) complexity
mnnit.rahul- Posts : 16
Join date : 2008-08-10
ankurgutpa- Posts : 44
Join date : 2008-08-10
Age : 36
Location : Tandon 72
@PAPA
how can it be 2n-1 largest sum
a[0]+b[5] can be smaller than a[1]+b[2]
a[0]+b[5] can be smaller than a[1]+b[2]
mnnit.rahul- Posts : 16
Join date : 2008-08-10
@Etawah
1. sum[0]=a[0]+b[0]
2.i=0,j=0,k=0
3. while(--n),
4.{ if(a[i]-a[i+1] > b[j]-b[j+1])
j++;
else
i++;
k++;
sum[k]=a[i]+b[j];
}
2.i=0,j=0,k=0
3. while(--n),
4.{ if(a[i]-a[i+1] > b[j]-b[j+1])
j++;
else
i++;
k++;
sum[k]=a[i]+b[j];
}
chunks- Posts : 6
Join date : 2008-08-14
Re: n largest sum
chunky's solution is wrong
i am unable to see any O(n) solution but optimized it as follows
let A={a,b,c,d}
B={p,q,r,s}
now consider the matrix of sums :
a+p a+q a+r a+s
b+p b+q b+r b+s
c+p c+q c+r c+s
d+p d+q d+r d+s
...
This matrix is sorted in decreasing order row-wise and column-wise
now largest n sums will be found in upper triangular matrix ie from n(n+1)/2 elements and remaining lower half n(n-1)/2 elements can be neglected. Now there can be at most 1 element (nth largest) from non-major diagonal ( ie max (a+s, b+r,c+q,d+p) ) This is O(n) step.Say we find out this element then also it is possible that this element does not exist in n largest sum
now etawah. tell us the answer
i am unable to see any O(n) solution but optimized it as follows
let A={a,b,c,d}
B={p,q,r,s}
now consider the matrix of sums :
a+p a+q a+r a+s
b+p b+q b+r b+s
c+p c+q c+r c+s
d+p d+q d+r d+s
...
This matrix is sorted in decreasing order row-wise and column-wise
now largest n sums will be found in upper triangular matrix ie from n(n+1)/2 elements and remaining lower half n(n-1)/2 elements can be neglected. Now there can be at most 1 element (nth largest) from non-major diagonal ( ie max (a+s, b+r,c+q,d+p) ) This is O(n) step.Say we find out this element then also it is possible that this element does not exist in n largest sum
now etawah. tell us the answer
Last edited by ankurgutpa on Wed Aug 20, 2008 8:29 am; edited 1 time in total
ankurgutpa- Posts : 44
Join date : 2008-08-10
Age : 36
Location : Tandon 72
implementation of that algo
we have to find n largest sums, which we can make using 1-1 elements from both arrays....???
if yes then ...try this,if anything is wrong then let me know:
otherwise explain me the question.
#include<iostream>
using namespace std;
int main()
{
int n,n1,i,j,k;
cin>>n;
n1=n;
int arr1[n],arr2[n],sum[n];
for(i=0;i<n;i++) cin>>arr1[i];
for(i=0;i<n;i++) cin>>arr2[i];
sum[0]=arr1[0]+arr2[0];
i=0,j=0,k=0;
while(--n)
{
if(arr1[i]-arr1[i+1] > arr2[j]-arr2[j+1])
j++;
else if(arr1[i]-arr1[i+1] == arr2[j]-arr2[j+1])
{
if(arr1[i]>arr2[j])
j++;
else
i++;
k++;
sum[k]=arr1[i]+arr2[j];
}
else
i++;
k++;
sum[k]=arr1[i]+arr2[j];
}
for(i=0;i<n1;i++)
cout<<i+1<<" largest sum:"<<sum[i]<<"\n";
cin>>i;
}
if yes then ...try this,if anything is wrong then let me know:
otherwise explain me the question.
#include<iostream>
using namespace std;
int main()
{
int n,n1,i,j,k;
cin>>n;
n1=n;
int arr1[n],arr2[n],sum[n];
for(i=0;i<n;i++) cin>>arr1[i];
for(i=0;i<n;i++) cin>>arr2[i];
sum[0]=arr1[0]+arr2[0];
i=0,j=0,k=0;
while(--n)
{
if(arr1[i]-arr1[i+1] > arr2[j]-arr2[j+1])
j++;
else if(arr1[i]-arr1[i+1] == arr2[j]-arr2[j+1])
{
if(arr1[i]>arr2[j])
j++;
else
i++;
k++;
sum[k]=arr1[i]+arr2[j];
}
else
i++;
k++;
sum[k]=arr1[i]+arr2[j];
}
for(i=0;i<n1;i++)
cout<<i+1<<" largest sum:"<<sum[i]<<"\n";
cin>>i;
}
chunks- Posts : 6
Join date : 2008-08-14
@All
haan yaar ankur...galat aa rha hai.....
koi decode karo yaar.....
koi decode karo yaar.....
Last edited by shivang on Wed Aug 20, 2008 10:29 am; edited 1 time in total
shivang- Posts : 22
Join date : 2008-08-11
Age : 35
Location : Tondon 174
Re: n largest sum
it's wrong again
chk for n=5
10,8,6,4,2
5,4,3,2,1
chk for n=5
10,8,6,4,2
5,4,3,2,1
ankurgutpa- Posts : 44
Join date : 2008-08-10
Age : 36
Location : Tandon 72
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum