you are right!!!
but i think there is a interesting thing hided in this problem.
let set[i] = {a[i]+b[1], a[i]+b[2], a[i]+b[3], ..., ai+an},
and MAX is the set of n largest numbers. if there
are some elements in the set[i] belong to the MAX,
we can know the number of these elements must be
less
Hi Arunachalam!
Good work! Is there some way you can stop duplicates in the final
answer? i.e; ai+bj can be considered more than once as answer.
Sorry, i am poor at mathematics so can't figure it out how to get its
running time.
But still there is some way that we can get O(n) even in worst
aamir 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
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) //
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
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)..
Hi,
It is very hard for me to get the basic flow of this algorithm. Can you explain the basic idea behind the algorithm.
regards
Arunachalam.
On 4/3/06, Mayur [EMAIL PROTECTED] wrote:
right... that's correct. Arunachalam's right... Sorry... My second attempt at it... One assumption, though -
Here is the improvement to my previous algorithm.
Observation 1.
ax+by can appear in the solution only if ax+bj has appeared in the solution where j y.
Observation 2.
ax+bn can be included only if a(x+1)+bn is included in the answer.
1. Extract an+bn as the maximum
2. Form a heap with
since A and B is sorted, we can do the merger step( in merge sort) in the reverse direction from end.the merger step in merge sort is linear.On 4/3/06,
Padmanabhan Natarajan [EMAIL PROTECTED] wrote:
This solution looks correct but its still not clear as to how it is linear.A totally different
ignore this msg. didnt read prob carefully :(On 4/3/06, Arun [EMAIL PROTECTED] wrote:
since A and B is sorted, we can do the merger step( in merge sort) in the reverse direction from end.the merger step in merge sort is linear.
On 4/3/06,
Padmanabhan Natarajan [EMAIL PROTECTED] wrote:
This
10 matches
Mail list logo
