You have n numbers b1, b2, . bi . , bn. Number bi has a weight wi . Give a linear time algorithm to find a number aj so that the total weight of numbers lesser and greater than bj is not more than half the total weight of the set.
I was asked this question in my college exam under divide and conquer algorithms but I was not able to solve it ?do you guys have any hints?
In the above question, I’m assuming that the mention of lesser and greater than are w.r.t position/Indexing.
SUM(W i’s) - W j <= 0.5*SUM(W i’s)
Time complexity for finding SUM(W i’s) is goining to be n.
The final step is going to be going through the Weight vector and checking wether if it satisfies the above mentioned condition.
In the case of lesser and greater than not being positions then the computation of SUM(W i’s) going to be the same, but some pre processing should be done with weight vector.
Consider only Unique values from A vector. Arrange weights in an incresing order w.r.t A vecotr values. Now follow the same procedure as did for the first method.
Hope this is right.
do you think divide and conquer is linear time algorithm?
file:///Users/amanmeena/Downloads/ALinearTimeAlgorithmfortheWeightedMedianProblem_10291589.pdf
this is what i found out
give the access to the this file
error showing : Your file couldn’t be accessed
see this if you are not able to access above file