One assumption, though - the output need not be sorted...
1: curMin <- min( a[0], b[0] ) - 1
2: i <- n, j<-n
3: cnt <- 0, whoSurged = NONE;
4: while ( cnt < n )
{
5: output a[i] + b[j]
6: cnt <- cnt + 1
7: if a[i] + b[j] < curMin
8: then if whoSurged == A
9: then j <- j - 1
10: i = n
11: else i <- i - 1
12: j = n
12.5: curMin = min(a[0], b[0]) - 1
13: goto step 4
14: if (a[i-1] + b[j]) < (a[i] + b[j-1])
15: then j <- j - 1
16: if curMin == (min(a[0], b[0]) -1 )
17: then whoSurged = B
18: curMin = a[i-1] + b[j+1]
19: else i <- i - 1
20: if curMin == (min(a[0], b[0]) -1 )
21: then whoSurged = A
22: curMin = a[i+1] + b[j-1]
}
On 4/3/06, iwgmsft <[EMAIL PROTECTED]> wrote:
assume we have set {ai+bj}.. of size n^2
we can solve using MERGE-SORT i think.. to divide this problem into
subproblems will take O(2logn) i.e. O(log n)...
now at the time of merge it will take O(2n) i.e . O(n)... so this time
we can find n largest values(by merging values in decending order)..
correct me if i m wrong..
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
