TopCoder problem "MissingDigits" used in TCHS SRM 51 (Division I Level One)



Problem Statement

    You are opening a new hotel and are in the process of numbering the rooms. Being a superstitious person, you don't want to allow certain numbers. You are given an int[] notAllowed containing an encoded list of forbidden sequences. The ith forbidden sequence (where i is a 0-based index) is the concatenation of decimal representations of i and notAllowed[i] (both with no extra leading zeros). For example, if the 0th element of notAllowed is 33, then "033" is a forbidden sequence. A room number is not allowed if its decimal string representation, with no extra leading zeroes, contains any of the forbidden sequences as a substring. Given an int roomNumber, return "YES" if the room number is allowed, and "NO" otherwise (all quotes for clarity).
 

Definition

    
Class:MissingDigits
Method:isAllowed
Parameters:int[], int
Returns:String
Method signature:String isAllowed(int[] notAllowed, int roomNumber)
(be sure your method is public)
    
 

Constraints

-notAllowed will contain between 0 and 50 elements, inclusive.
-Each element of notAllowed will be between 0 and 10000000, inclusive.
-roomNumber will be between 0 and 10000000, inclusive.
 

Examples

0)
    
{1}
101
Returns: "NO"
Since element 0 of notAllowed is 1, 01 is forbidden. Hence 101 is not a valid room number.
1)
    
{1,33,7}
7133
Returns: "NO"
Element 1 of notAllowed is 33, so 133 is forbidden.
2)
    
{1,32,67}
267
Returns: "NO"
Element 2 of notAllowed is 67, so 267 is forbidden.
3)
    
{1,33,7}
68
Returns: "YES"
4)
    
{0}
0
Returns: "YES"
"00" is forbidden, but single 0 is allowed.
5)
    
{1245,2481,1271,1463,557,1544,1462,1710,988,2167,
 1013,736,1816,702,388,207,333,27,349,1659,1818,
 1227,1893,1916,1430,1630,893,651,2142,987,631,
 2290,1267,656,1912,343,1339,1938,753,2150,576,
 76,801,1270,2266,2415,188,1595,1749,2019}
2026595
Returns: "YES"
6)
    
{1245,2481,1271,1463,557,1544,1462,1710,988,2167,
 1013,736,1816,702,388,207,333,27,349,1659,1818,
 1227,1893,1916,1430,1630,893,651,2142,987,631,
 2290,1267,656,1912,343,1339,1938,753,2150,576,
 76,801,1270,2266,2415,188,1595,1749,2019}
4312703
Returns: "NO"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7920

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13484&pm=7920

Writer:

Ishan

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Math