# 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++/Java:

## 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%

## Java

Output (will vary):

1 ~ 29.956%
2 ~ 10.0081%
3 ~ 20.006%
4 ~ 15.0369%
5 ~ 24.993%     (2 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest
marshall

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