[algogeeks] Re: I guess, It is a tough one!!! Lets see who solves this

Sun, 02 Apr 2006 23:36:58 -0700

I dont agree with Mayur. If this solution generates first two large numbers as an+bn, a(n-1)+bn then this solution will not take into consideration the number an+(bn-1). Which is not correct.
 
regards
Arunachalam.

 
On 4/3/06, Mayur <[EMAIL PROTECTED]> wrote:
I donno if it's so tough... Maybe I'm wrong.! Or I may have missed on something. Here's my attempt.
We have a0 <= a1 <= ... <= an
and         b0 <= b1 <= ... <= bn

Therfore, the largest ai + bj would be (an + bn)

1: count <- 0
2: i <- n, j <- n
2: while count < n
3:       select ai + bj.
4:       if a(i-1) < b(j-1)    // ofcourse, the boundary conditions are missing - easy to put them..
5:             then j <- j -1
6:             else i <- i-1
7:       count <- count + 1

i.e. the next largest ai+bj, after an+bn would either be a(n-1)+bn, or an+b(n-1). Choose to use the one which maximizes the sum. It's a simple greedy algorithm.




On 4/3/06, aamir <[EMAIL PROTECTED]> wrote:

Two sets {ao,a1,a2,..an} and {b0,b1,b2,...bn} having integers in
increasing order (Sorted arrays of size n).

We have to select n largest numbers from the set {ai+bj} ( This set is
the sum of two numbers one taken from set A and one taken from set B.It
is obvious that this set is n^2 in size).Our task is to get n largest
numbers in O(n.log(n)).
It can also be solved in O(n).So second step of this problem is to
develop algo in O(n).

PLEASE DONT WRITE COMPLETE CODE JUST BRIEFLY EXPLAIN THE ALGO.Coz it is
easier for everybody to understand.Thanks







http"//ww.livejournal.com/users/arunachalam
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---

Reply via email to