UnluckyNumbers
SRM 438 · 2009-04-18 · by vexorian
SRM 438 · 2009-04-18 · by vexorian · Math, Simple Search, Iteration, Sorting
Problem Statement
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 aint[] 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.
Given a
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
4)
{935,273,796,757,284,782,415,425,189,278,241,402,903,827}
93
Returns: 8927
Submissions are judged against all 146 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class UnluckyNumbers with a public method int getCount(vector<int> luckySet, int n) · 146 test cases · 2 s / 256 MB per case