0
$\begingroup$

So I'm having some discrete elements X1,X2,...,Xn with positive weights Wi (all weights sum up to 1). The weighted average is an element Xk that:

enter image description here

What I want is an algorithm to calculate that Xk in O(nlogn) time with the use of sorting algorithm.

Any ideas to give me a boost? I don't want the whole solution, just something to get it started.

Thanks

Improve this question
$\endgroup$
  • 1
    $\begingroup$ What did you try? Where did you get stuck? Have you tried working through some examples? What happens if you sort the elements by their value Xi? What happens if you sort them by their weights Wi? Does either one help you solve the problem? Try some small examples by hand and see. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W.♦ Apr 5 '18 at 16:28
  • $\begingroup$ Sort the list by value, compute running totals of weight, and run binary search. $\endgroup$ – Yuval Filmus Apr 5 '18 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.