TopCoder problem "InputBoxChecker" used in SRM 310 (Division II Level Two)



Problem Statement

    

Imagine a simple input dialog box. The user is supposed to enter a positive integer from a given range into the box.

Recently you realized that sometimes you can tell that the user's input is invalid before he finishes entering the number. For example, if the valid range is 300 to 347, and the user wants to enter the number 372, as soon as he types "37" you can be sure that his input won't be valid.

More precisely, we call a number valid if it is a prefix of some number in the given range, and invalid otherwise.

You are given two ints smallest and largest (denoting the range of valid inputs), and a int[] numbers. The range of valid inputs contains all integers between smallest and largest, inclusive.

Write a method that will determine for each number in numbers whether it represents a valid input for the given range. Return a String[] that has the same number of elements as numbers. If the i-th element of numbers represents a valid input, the i-th element of the return value has to be "VALID", otherwise it has to be "INVALID" (quotes for clarity only).

 

Definition

    
Class:InputBoxChecker
Method:checkPrefix
Parameters:int, int, int[]
Returns:String[]
Method signature:String[] checkPrefix(int smallest, int largest, int[] numbers)
(be sure your method is public)
    
 

Constraints

-smallest is between 1 and 2,000,000,000, inclusive.
-largest is between 1 and 2,000,000,000, inclusive.
-smallest is less than or equal to largest.
-numbers contains between 1 and 50 elements, inclusive.
-Each element in numbers is between 1 and 2,000,000,000, inclusive.
 

Examples

0)
    
300
347
{37}
Returns: {"INVALID" }
This is the example from the problem statement.
1)
    
310
320
{3, 31, 317, 3174, 310, 320}
Returns: {"VALID", "VALID", "VALID", "INVALID", "VALID", "VALID" }
Please note that smallest and largest represent an inclusive range.
2)
    
600
1020
{7, 73, 734, 7349}
Returns: {"VALID", "VALID", "VALID", "INVALID" }
3)
    
64
78
{1,2,3,4,5,6,7,8,9}
Returns: 
{"INVALID",
"INVALID",
"INVALID",
"INVALID",
"INVALID",
"VALID",
"VALID",
"INVALID",
"INVALID" }
4)
    
1
1234567890
{123, 456, 789, 1234567, 7654321, 3245354, 325432532, 243212}
Returns: {"VALID", "VALID", "VALID", "VALID", "VALID", "VALID", "VALID", "VALID" }
Watch out for the time limit.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9990&pm=6542

Writer:

misof

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Greedy, Simple Math