DrawingMarbles | Topcoder Archive

Problem Statement

A big box contains marbles of one or more colors. You're given a int[] colors, each element of which denotes the number of marbles there are of a particular color. You draw n marbles randomly from the box, leaving each marble outside the box after taking it. Return the probability that all marbles drawn will be the same color.

Definition

Class:: DrawingMarbles
Method:: sameColor
Parameters:: int[], int
Returns:: double
Method signature:: double sameColor(int[] colors, int n)
(be sure your method is public)

Notes

Every time we draw a marble, all marbles in the box are equally likely to be chosen.
A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.

Constraints

colors will contain between 1 and 50 elements, inclusive.
Each element of colors will be between 1 and 50, inclusive.
n will be between 1 and the sum of all elements of colors, inclusive.

Examples

```
{ 13 }
```
```
8
```
```
Returns: 1.0
```
All the marbles are the same color, so obviously all drawn marbles will be the same color too.
```
{ 5, 7 }
```
```
1
```
```
Returns: 1.0
```
```
{ 5, 6, 7 }
```
```
2
```
```
Returns: 0.3006535947712418
```
The probability that the first drawn marble will be of the color 0 is 5 / 18 (there are 5 marbles of color 0 out of 18). If the first drawn marble is of the color 0, then the probability that the second drawn marble will be of the color 0 is 4 / 17 (there are 4 marbles of color 0 left out of 17). So the probability that both drawn marbles will be of the color 0 is (5 / 18) * (4 / 17) = 0.0653594771... . Similarly, the probability that both drawn marbles will be of the color 1 is (6 / 18) * (5 / 17) = 0.0980392156..., and that both drawn marbles will be of the color 2 is (7 / 18) * (6 / 17) = 0.1372549019... . The answer is the sum of these 3 probabilities.

{ 12, 2, 34, 13, 17 }

Returns: 0.035028830818304504

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.