TopCoder problem "UnluckyNumbers" used in SRM 438 (Division II Level One)



Problem Statement

    You are given a set of integers called luckySet. An interval [A,B], where B is greater than A, and A and B are positive integers, is considered unlucky if none of the integers between A and B, inclusive, belongs to luckySet.



Given a int[] luckySet and a int n that is not greater than the maximum element in luckySet. Return the total number of unlucky intervals that contain n.
 

Definition

    
Class:UnluckyNumbers
Method:getCount
Parameters:int[], int
Returns:int
Method signature:int getCount(int[] luckySet, int n)
(be sure your method is public)
    
 

Constraints

-luckySet will contain between 2 and 50 elements, inclusive.
-Each element of luckySet will be between 1 and 1000, inclusive.
-Each element of luckySet will be distinct.
-n will be between 1 and the largest element in luckySet, inclusive.
 

Examples

0)
    
{1, 7, 14, 10}
2
Returns: 4
4 unlucky intervals in total contain 2:

[2,3], [2,4], [2,5] and [2, 6].
1)
    
{4, 8, 13, 24, 30}
10
Returns: 5
The five unlucky intervals that contain 10 are:

[9, 10], [9, 11], [9, 12], [10, 11] and [10, 12].
2)
    
{10, 20, 30, 40, 50}
30
Returns: 0
By definition, no unlucky interval can contain 30.
3)
    
{3, 7, 12, 18, 25, 100, 33, 1000}
59
Returns: 1065

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13803&pm=10396

Writer:

vexorian

Testers:

PabloGilberto , ivan_metelsky , ged

Problem categories:

Math, Simple Search, Iteration, Sorting