n largest sum

Go down

n largest sum

Post  mnnit.rahul on Wed Aug 13, 2008 11:45 am

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

mnnit.rahul

Posts : 16
Join date : 2008-08-10

View user profile

Back to top Go down

Re: n largest sum

Post  ankurgutpa on Wed Aug 13, 2008 1:05 pm

cheers


Last edited by ankurgutpa on Sun Aug 17, 2008 1:31 pm; edited 1 time in total
avatar
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 31
Location : Tandon 72

View user profile

Back to top Go down

@PAPA

Post  mnnit.rahul on Thu Aug 14, 2008 2:09 am

how can it be 2n-1 largest sum
a[0]+b[5] can be smaller than a[1]+b[2]

mnnit.rahul

Posts : 16
Join date : 2008-08-10

View user profile

Back to top Go down

@Etawah

Post  chunks on Thu Aug 14, 2008 7:00 am

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];
}
Very Happy
avatar
chunks

Posts : 6
Join date : 2008-08-14

View user profile

Back to top Go down

@CHACHI

Post  prani on Sun Aug 17, 2008 1:00 pm

chunky samjhao bhai......

prani

Posts : 15
Join date : 2008-08-12

View user profile

Back to top Go down

Re: n largest sum

Post  ankurgutpa on Sun Aug 17, 2008 1:30 pm

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 pale
now etawah. tell us the answer cheers


Last edited by ankurgutpa on Wed Aug 20, 2008 8:29 am; edited 1 time in total
avatar
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 31
Location : Tandon 72

View user profile

Back to top Go down

implementation of that algo

Post  chunks on Sun Aug 17, 2008 2:34 pm

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;
}
avatar
chunks

Posts : 6
Join date : 2008-08-14

View user profile

Back to top Go down

@All

Post  shivang on Mon Aug 18, 2008 9:44 am

haan yaar ankur...galat aa rha hai.....
koi decode karo yaar..... Sleep Exclamation


Last edited by shivang on Wed Aug 20, 2008 10:29 am; edited 1 time in total
avatar
shivang

Posts : 22
Join date : 2008-08-11
Age : 29
Location : Tondon 174

View user profile

Back to top Go down

Re: n largest sum

Post  ankurgutpa on Wed Aug 20, 2008 8:27 am

it's wrong again
chk for n=5
10,8,6,4,2
5,4,3,2,1 cheers
avatar
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 31
Location : Tandon 72

View user profile

Back to top Go down

Re: n largest sum

Post  Sponsored content


Sponsored content


Back to top Go down

Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum