Algorithm

 Problem Statement for TheLotteryBothDivs

Problem link- https://community.topcoder.com/stat?c=problem_statement&pm=11359&rd=14431

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 & Try With Live Editor

Input

x
–
+
cmd
{"4"}

Output

x
–
+
cmd
0.1
Advertisements

Demonstration

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