Guys no one commented on my solution? Any takes on it?
Anyways, below is my solution (in pseudo code)
Pre-condition: A and B are sequences of equal length and sorted in
descending order
Input: Sequences A[1..N] and B[1..N] of equal lengths(N)
Ouput: Sequence C[1..N] containing sorted sum of ordered pairs from
cartesian products of A, B or B,A
Sort(A,B)
{
k = 1
N = length(A) = length(B)
C[1..2*N] = [] // Empty array
cart_prod_order = 0 // 0 -> AxB, 1 -> BxA. 0 is default
// Complexity : O(N)
while(k != N+1)
{
if (A[k] < B [k])
{
cart_prod_order = 1
break
}
else
{
k = k + 1
}
}
// Choose the correct order of Cartesian product sum
// Complexity: Theta(2N) = O(N)
if (cart_prod_order == 1)
{
// take cartesian product of B and A, storing the sum of ordered
pair (b,a) in each element of C
C[1..2N] = B[1..2] x A[1..N]
}
else
{
// take cartesian product of A and B, storing the sum of ordered
pair (a,b) in each element of C
C[1..2N] = A[1..2] x B[1..N]
}
// Merge
// C[1..N] and C[N+1..2N] are already sorted in descending order
// Complexity: Theta(N)
C[1..2N] = Merge(C[1..N],C[N+1..2N])
return C[1..N]
}
Merge(C,D)
{
i=1,j=1,k=1
E = []
while(i<=length(C) OR j<=length(D))
{
if(i<=length(C) AND (j>length(D) OR C[i]>D[j]))
{
E[k] = C[i]
i = i + 1
}
else
{
E[k] = D[j]
j = j + 1
}
k = k + 1
}
return E;
}
On Fri, Apr 30, 2010 at 7:50 PM, banu <[email protected]> wrote:
> Nice question:
>
> 1. |A| = |B| i.e I assume their cardinality is equal
>
> 2. A(n) = { a1, a2 a3, ...aN} such that a1>=a2>=a3...>=aN
> 3. B(n) = { b1, b2 b3, ...bN} such that b1>=b2>=b3...>=bN
>
> 4. S(n^2) = A x B = {(a1,b1), (a1,b2)....(a1,bN),
> (a2,b1), (a2,b2)....(a2,bN),
> ....
> (aN,b1), (aN,b2)....(aN,bN)}
>
> assuming we have added in a way such that we find a pair ai > bi,
> for some i in 1..N such that a(i-1) = b(i-1)
>
> A first observation is that in the worst case, the first 2N numbers in
> S will contain the final result of N numbers.
> i.e in (a1,b1), (a1,b2)....(a1,bN), (a2,b1), (a2,b2)....(a2,bN)
>
> In the best case first N numbers in S will contain the final N numbers
> (already sorted in decreasing order)
> i.e in (a1,b1), (a1,b2)....(a1,bN)
>
> Now, if we consider again the worst case scenario, then we can first
> divide 2N numbers in two groups of size N each and each of this group
> is already sorted in decreasing order.
> i.e (a1,b1), (a1,b2)....(a1,bN) and (a2,b1), (a2,b2)....(a2,bN)
>
> Now we can simply apply Merge Algorithm on these 2 already sorted
> arrays of size N each in O(N) time, which solves the problem
>
> I can be wrong only if the the results lie outside first 2N
> numbers(which I hope is not the case).
>
>
> On Apr 30, 2:05 pm, divya <[email protected]> wrote:
>> Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's
>> say they are decreasingly sorted), we define a set S = {(a,b) | a \in
>> A
>> and b \in B}. Obviously there are n^2 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. The tricky part is that we need an O(n)
>> algorithm.
>>
>> --
>> 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
>> athttp://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.
>
>
--
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.
