@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`" <vipe...@gmail.com> 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 <rajuljain...@gmail.com> 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 <
>
> > bagana.bharatku...@gmail.com> 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 <macatad...@gmail.com> 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
> > >> <navneetn...@gmail.com>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 algogeeks@googlegroups.com.
> > >>> To unsubscribe from this group, send email to
> > >>> algogeeks+unsubscr...@googlegroups.com.
> > >>> 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 algogeeks@googlegroups.com.
> > >> To unsubscribe from this group, send email to
> > >> algogeeks+unsubscr...@googlegroups.com.
> > >> 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*
> > > <bagana.bharatku...@gmail.com>
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
