## Algorithm

Problem Statement for TheLotteryBothDivs

### Problem Statement

Farmer John wants to buy a lottery ticket. Before he buys a ticket, Fox Brus decided to calculate the probability that John will get a prize.

There are 1,000,000,000 types of lottery tickets. They are numbered "000000000" to "999999999" (they may have leading zeroes). Each type of ticket has an equal probability of being bought by John. You are given a String[] goodSuffixes. If the number written on John's ticket has at least one element of goodSuffixes as a suffix, he will get a prize.

Return the probability that John will get a prize.

### Definition

 Class: TheLotteryBothDivs Method: find Parameters: String[] Returns: double Method signature: double find(String[] goodSuffixes) (be sure your method is public)

### Notes

- The returned value must have an absolute or relative error less than 1e-9.
- A suffix of a string is obtained by removing zero or more contiguous characters from the beginning of the string.

### Constraints

- goodSuffixes will contain between 1 and 50 elements, inclusive.
- Each element of goodSuffixes will contain between 1 and 9 characters, inclusive.
- Each character in goodSuffixes will be a digit ('0'-'9').

### Examples

0)

 `{"4"}`
`Returns: 0.1`
 John will get a prize if the last digit is '4'. It happens with probability 0.1.
1)

 `{"4", "7"}`
`Returns: 0.2`
2)

 `{"47", "47"}`
`Returns: 0.01`
 goodSuffixes may contain duplicate elements.
3)

 `{"47", "58", "4747", "502"}`
`Returns: 0.021`
4)

 `{"8542861", "1954", "6", "523", "000000000", "5426", "8"}`
`Returns: 0.201100101`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class TheLotteryBothDivs {
public:
double find(vector <string> goodSuffixes) {
sort(goodSuffixes.begin(), goodSuffixes.end());
goodSuffixes.resize(unique(goodSuffixes.begin(), goodSuffixes.end()) - goodSuffixes.begin());

for(int i = 0; i < goodSuffixes.size(); ++i)
for(int j = 0; j < goodSuffixes.size(); ++j)
if(i != j && goodSuffixes[j].size() >= goodSuffixes[i].size() &&
goodSuffixes[j].substr(goodSuffixes[j].size() - goodSuffixes[i].size()) == goodSuffixes[i]) {
goodSuffixes.erase(goodSuffixes.begin() + j);
i = -1;
break;
}

double ret = 0;
for(int i = 0; i < goodSuffixes.size(); ++i)
ret += pow(10, 9 - goodSuffixes[i].length()) / pow(10, 9);

return ret;
}
};``````
Copy The Code &

Input

cmd
{"4"}

Output

cmd
0.1
Advertisements

## Demonstration

TopCoder Solution SRM502-D2-500 TheLotteryBothDivs C,C++, Java, Js and Python ,SRM502-D2-500,TopCoder Solution