Problem Statement
Misko and Danka are playing with a D-sided die. The die has faces numbered from 1 to D and it is a fair die: whenever rolled, each number will come up with probability 1 / D.
In their current game Misko is repeatedly rolling the die and Danka is taking notes as follows: After the very first roll, she does nothing. After each of the following rolls, she writes down the (non-negative) difference between the current and the previous outcome.
You are given the int D. You are also given the int[] rolled: the sequence of outcomes of rolls Misko already made, in chronological order.
Misko knows that Danka will not be happy until she has seen each possible difference occur at least once. He now wonders how many additional rolls this will take. Calculate and return the expected number of extra rolls needed until Danka will be happy.
Definition
- Class:
- SeeAllDifferences
- Method:
- solve
- Parameters:
- int, int[]
- Returns:
- double
- Method signature:
- double solve(int D, int[] rolled)
- (be sure your method is public)
Notes
- Your answer will be accepted if it has an absolute or a relative error at most 10^(-9).
Constraints
- D will be between 2 and 16, inclusive.
- rolled will contain between 1 and 50 elements, inclusive.
- Each element of rolled will be between 1 and D, inclusive.
Examples
2
{1,2,1}Returns: 2.0
The kids have a 2-sided die, i.e., a coin with sides labelled 1 and 2. Misko already tossed the coin three times. Danka has already written down the difference 1 twice. In order for Danka to be happy, she also needs to see the difference 0. In each of the following coin tosses this will happen with probability 1/2. From this, we can show that the expected number of coin tosses until it happens is 1 / (1/2) = 2.6
{3, 3, 4, 6, 1, 5, 2, 3, 4, 2, 2, 6}Returns: 0.0
Danka has already been happy for a while: here, the first six differences have already all been distinct.4
{2}Returns: 11.896969696969695