int npairs()
{
int a[] = {0,1,4,5,9,11,20};
int b[] = {0,2,3,6,8,11,15};
int c[20];
int len = sizeof(a)/sizeof(a[0]);
int i1,j1,i2,j2;
i1=len-1;
j1=len-2;
i2=len-2;
j2=len-1;
int count = 0;
c[count++] = a[len-1]+b[len-1]; //obvious
while(count<=len)
{
if( (a[i1-1]+b[j2-1] > a[i1]+b[j1]) && (a[i1-1]+a[j2-1] > a[i1]+b[j1]) )
{
c[count++] = a[i1-1]+b[j2-1]; //highest sum with higher numbers
have exhausted
i1 = i1-1,j2=j2-1,j1=j2-1,i2=i1-1;
continue;
}
if(a[i1]+b[j1] >= a[i2]+b[j2] )
{
c[count++] = a[i1]+b[j1];
j1--;
}
else
{
c[count++] = a[i2]+b[j2];
i2--;
}
}
for(int i =0;i<len;i++)
printf("%d ",c[i]);
return 0;
}
On Fri, Sep 2, 2011 at 8:37 AM, Navneet <[email protected]> wrote:
> Okay, I guess this question will be more tough to tackle in complete
> generality. in two sorted arrays, lets assume elements are in strictly
> increasing order, hence the extra care of duplicates in either array
> is gone. However, the same element can be present in both arrays.
>
> For ex.
> {1,2,3} {2,3,4}
>
> The duplicate case can obviously be solved, but i am not sure if we
> can have O(n) time bound in that case.
>
> On Sep 2, 3:36 am, "icy`" <[email protected]> wrote:
> > @Dave thanks for clarifying that (4,3) is different from (3,4)
> >
> > But let's suppose, for example, n is 3
> > so A is of size n, and B is of size n, as required
> > e.g. A = [1 1 2] , B = [1 2 2]
> >
> > S = { (1,1) (1,2) (1,2) (1,1) (1,2) (1,2) (2,1) (2,2) (2,2) }
> >
> > but now you see there are repeated points that are also in the same
> > order. These are duplicates and should be removed, if S is truly a
> > set. Pruned version:
> >
> > S = { (1,1) (1,2) (2,1) (2,2) }
> >
> > size of set is not n^2, or 9, but rather
> > (size of unique(A) ) * (size of unique(B) ) = 4
> >
> > With this in mind, I would first eliminate or ignore duplicates as you
> > are iterating through A, B
> >
> > On Sep 1, 5:50 pm, Dave <[email protected]> wrote:
> >
> >
> >
> >
> >
> >
> >
> > > @Icy: You left off the pairs (3,4), (2,4), (2,3), (1,4), (1,3), and
> > > (1,2). These are different than the pairs you listed, because they are
> > > ordered: the first element is from set A and the second element is
> > > from set B. This was masked because of your choice of A = B. But you
> > > wouldn't have made that mistake if you had chosen A = [1 2 3 4] and B
> > > = [5 6 7 8].
> >
> > > There is no restriction in the original problem statement that the
> > > numbers in each array are distinct. One application I have seen of
> > > this problem is with the travel reservation web sites, where they will
> > > show you some number of the cheapest round trip flight combinations.
> > > In that case, there is more to the data items than just the price,
> > > including at least airline and flight time. Several different flights
> > > might have the same price, so arrays like A = [1 1 2 3 3 3 3] and B =
> > > [1 2 2 2 3 3 4 4 4 4] (with duplicate prices) are possible. In that
> > > case, the first 2 (cheapest) round trips will have score 2. Then
> > > follows 7 round trips with score 3. Etc.
> >
> > > Dave
> >
> > > On Sep 1, 4:12 pm, "icy`" <[email protected]> wrote:
> >
> > > > actually this makes me think about the question requirements a bit..
> > > > in math, arent sets supposed to have *unique* elements?
> >
> > > > so if A= [ 1 2 3 4] , B= [ 1 2 3 4], then shouldnt
> > > > S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
> > > > (1,1) } ??
> >
> > > > since A is equal to B, the size of S is (4 choose 2) plus the four
> > > > mirror pairs, so 6+4 = 10
> >
> > > > and the question implies mathematical sets with that notation, so why
> > > > are there necessarily n squared elements in S ...?
> >
> > > > On Sep 1, 2:01 pm, rajul jain <[email protected]> wrote:
> >
> > > > > @bharat I think pair of your example would be (4,4) , (4,3)
> ,(3,4),
> > > > > (3,3)....
> > > > > correct me if am wrong..
> >
> > > > > On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana <
> >
> > > > > [email protected]> wrote:
> > > > > > @Mac: It gives us the first largest pair but need not all n pairs
> ..
> > > > > > ex:
> > > > > > A=1 1 3 4
> > > > > > B=1 2 3 4
> > > > > > pairs : (4,4),(4,3),(3,3),(2,4) .....
> >
> > > > > > On Thu, Sep 1, 2011 at 4:57 AM, MAC <[email protected]>
> wrote:
> >
> > > > > >> since its sorted , cant we just take last (largest if assedning)
> elements
> > > > > >> of each and return o(1) .. (since +ve we can do so i guess)
> >
> > > > > >> On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta <
> [email protected]>wrote:
> >
> > > > > >>> Given two sorted positive integer arrays A(n) and B(n), we
> define a
> > > > > >>> set S = {(a,b) | a in A and b in B}. Obviously there are n2
> elements
> > > > > >>> in S. The value of such a pair is defined as Val(a,b) = a + b.
> Now we
> > > > > >>> want to get the n pairs from S with largest values. need an
> O(n)
> > > > > >>> algorithm.
> >
> > > > > >>> --
> > > > > >>> Regards,
> > > > > >>> Navneet
> >
> > > > > >>> --
> > > > > >>> 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.
> >
> > > > > >> --
> > > > > >> thanks
> > > > > >> --mac
> >
> > > > > >> --
> > > > > >> 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.
> >
> > > > > > --
> >
> > > > > > **Please do not print this e-mail until urgent requirement. Go
> Green!!
> > > > > > Save Papers <=> Save Trees
> > > > > > *BharatKumar Bagana*
> > > > > > **http://www.google.com/profiles/bagana.bharatkumar<
> http://www.google.com/profiles/bagana.bharatkumar>
> > > > > > *
> > > > > > Mobile +91 8056127652*
> > > > > > <[email protected]>
> >
> > > > > > --
> > > > > > 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.-Hidequoted text -
> >
> > > > - Show quoted text -
>
> --
> 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.
>
>
--
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.
