TopCoder problem "ConsecutiveNumbers" used in SRM 402 (Division II Level Two)



Problem Statement

    

Your little son has written some consecutive positive integers on a piece of paper, in no particular order. Each integer was written exactly once. He then erased one of the integers and showed you the remaining ones. Do you know which number your son erased?

Formally, a list of positive integers is said to be consecutive if there are two positive integers a and b such that every integer between a and b, inclusive, appears in the list exactly once.

For example, if the remaining numbers are (10,7,12,8,11), the only possible missing number is 9. If the remaining numbers are (2,3), the missing number could be either 1 or 4. If the remaining numbers are (3,6), your son must have made a mistake.

You are given the remaining numbers in a int[] numbers. Return a int[] containing all the possible numbers your son might have erased. The numbers should be sorted in ascending order, and there should be no duplicates. If your son made a mistake, return an empty int[].

 

Definition

    
Class:ConsecutiveNumbers
Method:missingNumber
Parameters:int[]
Returns:int[]
Method signature:int[] missingNumber(int[] numbers)
(be sure your method is public)
    
 

Constraints

-numbers will contain between 1 and 50 elements, inclusive.
-Each element of numbers will be between 1 and 1000000000, inclusive.
 

Examples

0)
    
{10,7,12,8,11}
Returns: {9 }
The first example in the problem statement.
1)
    
{3,6}
Returns: { }
The third example in the problem statement.
2)
    
{5,6,7,8}
Returns: {4, 9 }
There original list might be {4,5,6,7,8} or {5,6,7,8,9}.
3)
    
{1000000000}
Returns: {999999999, 1000000001 }
4)
    
{1,6,9,3,8,12,7,4,11,5,10}
Returns: {2 }
5)
    
{1}
Returns: {2 }
Only positive integers are allowed.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12174&pm=8302

Writer:

srbga

Testers:

PabloGilberto , Olexiy , ivan_metelsky , Gassa

Problem categories:

Brute Force, Simple Search, Iteration, Sorting