Test if an event is in the x% most probable
Given the unsorted array arr containing the probability of n events, how to check if a given event is amongst the x% most probable events ?
For example, for n=3 and arr={0.3, 0.2, 0.5} (the event #0 occurs 30% of the time, event #1 20%, event #2 50%):
- Check(event=0, x=0.1): Is the event #0 in the top 10% of events ? Event #2 is the most probable and occurs 50% of the time, so no.
- Check(event=0, x=0.6): Is the event #0 in the top 60% of events? Events #2 and event #0 are the two most probable events and occurs together 80% of the time, so yes.
Try by yourself before displaying the solution by clicking here !
The obvious solution is to sort the array from most probable to less probable, then iterate on the array while adding up the probabilities, until the sum becomes larger than x (in which case return false), or the iteration reaches the event (in which case return true).
But it requires to sort the array which is expensive. It is possible to do it without sorting the array.
Try by yourself before displaying a faster solution by clicking here !
When you're adding up the probabilities in the sorted array from the most probable to the less one, what you're really doing is simply adding the probabilities which are larger than the probability of the event in argument. There is no need for the array to be sorted to perform this calculation: iterate on the unsorted array and add the probability if it's larger than the one of the event. If the sum becomes larger than x return false, else return true.
2022-07-11
in
All,
Riddle,
52 views
