@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 <dave_and_da...@juno.com> 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`" <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.
