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
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
