TCPhoneHomeEasy
SRM 722 · 2017-10-11 · by erinn
Problem Statement
Typically, telephone numbers are sequences of digits (0-9) that all have the same length. However, some prefixes may be reserved for special purposes. This limits the total number of possible full-length telephone numbers that are available for general use in the system.
As an example, in much of the United States and Canada the local telephone numbers are 7 digits long. However, dialing 1 starts a special sequence for long distance, dialing 0 connects to the operator, and dialing 911 connects to emergency services. Thus, there are fewer than the theoretical 10,000,000 possible valid telephone numbers.
You are given the
Compute and return the number of different standard telephone numbers in the system.
Constraints
- digits will be between 1 and 7, inclusive.
- specialPrefixes will contain beteween 0 and 50 elements, inclusive.
- The length of each element of specialPrefixes will be between 1 and digits, inclusive.
- Each character of each element of specialPrefixes will be a digit ('0'...'9').
- No element of specialPrefixes will itself be a prefix of another element.
7
{ "0", "1", "911" }
Returns: 7990000
This is the example from the problem statement.
5
{ "0", "1", "911" }
Returns: 79900
Same prefixes, but with shorter phone numbers.
6
{ "1", "2", "3" }
Returns: 700000
6
{ "1", "23", "345" }
Returns: 889000
7
{}
Returns: 10000000
3
{"411"}
Returns: 999
Sometimes a special "prefix" is actually a full length phone number.
Submissions are judged against all 23 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TCPhoneHomeEasy with a public method int validNumbers(int digits, vector<string> specialPrefixes) · 23 test cases · 2 s / 256 MB per case