Problem Statement
You have a biased die with N faces, labeled 0 to N-1. You are given the int[] die with the relative probabilities of rolling each value. I.e., on this die you will roll the value x with probability die[x] / sum(die).
You are given the String goal. You are going to repeatedly roll your die and write down the result until the last length(goal) characters match goal exactly.
The expected number of rolls in the above process can be written as a reduced fraction P/Q. Return P*Q^(-1) modulo (10^9 + 7).
Definition
- Class:
- RollMe
- Method:
- solve
- Parameters:
- int[], String
- Returns:
- int
- Method signature:
- int solve(int[] die, String goal)
- (be sure your method is public)
Notes
- The exact answer is always a rational number. If we write it as a simplified fraction P/Q, the value Q will always be relatively prime to 10^9 + 7. Hence, Q has a multiplicative inverse: a value Q^(-1) such that (Q*Q^(-1)) mod (10^9 + 7) = 1.
Constraints
- N will be between 2 and 10, inclusive.
- die will have N elements.
- Each element of die will be between 1 and 10, inclusive.
- goal will have between 1 and 5000 characters, inclusive.
- Each character of goal will be one of the N smallest digits ('0', '1', ...).
Examples
{7, 7}"01"
Returns: 4
A fair coin. We are waiting until we see a head ('0') followed by a tail ('1'). This takes four flips on average.{1, 1}"00"
Returns: 6
Another fair coin, but now we are waiting for two heads in a row. Perhaps surprisingly, that requires 6 coin flips on average: more than another pattern of the same length.{2, 1}"1011"
Returns: 500000047
On average we'll need to make 43.5 = 87/2 coin flips with this biased coin until "1011" appears. We have P=87 and Q=2. The multiplicative inverse to this Q is Q^(-1) = 500,000,004, and thus the correct return value is (87 * 500000004) mod 1000000007 = 500,000,047.{1, 1, 1, 1, 1}"0123401"
Returns: 78150