# Generate Random Input from an Array according to given Probabilities

Write an algorithm to generate any one of the given N numbers according to given probabilities.

For example, consider the below array of integers and their probabilities:

input[] = { 1, 2, 3, 4, 5 };
probability[] = { 30, 10, 20, 15, 25 }; // total probability should sum to 100%

The solution should return `1` with `30%` probability, `2` with `10%` probability, `3` with `20%` probability, and so on for every element in the array.

##### Algorithm:
1. Construct an sum array `S[]` from the given probability array `P[]` where `S[i]` holds the sum of all `P[j]` for `0 <= j <= i`.

2. Generate a random integer from `1` to `100` and check where it lies in `S[]`.

3. Based on the comparison result, return the corresponding element from the input array.

Below is its implementation in C/C++:

## C

Output (will vary):

1 ~ 29.96%
2 ~ 10.05%
3 ~ 20.04%
4 ~ 14.91%
5 ~ 25.04%

## C++

Output (will vary):

1 ~ 30.017%
2 ~ 10.0539%
3 ~ 20.0162%
4 ~ 14.9635%
5 ~ 24.9494%

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Get great deals at Amazon

Notify of
Guest
marshall

Since the `prob_sum` vector is sorted, you can use `binary_search` or `lower_bound` instead of scanning linearly.

Guest