Connection Status:
Competition Arena > ConsecutiveNumbers

ConsecutiveNumbers

SRM 402 · 2008-05-24 · by srbga

SRM 402 · 2008-05-24 · by srbga · Brute Force, Simple Search, Iteration, Sorting
Class Name: ConsecutiveNumbers
Return Type: int[]
Method Name: missingNumber
Arg Types: (vector<int>)
Problem Statement

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[].

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)
{5,5}
Returns: { }

no duplications

6)
{1}
Returns: {2 }

Only positive integers are allowed.

9)
{1,3,5}
Returns: { }

only one gap

Submissions are judged against all 186 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ConsecutiveNumbers with a public method vector<int> missingNumber(vector<int> numbers) · 186 test cases · 2 s / 256 MB per case

Submitting as anonymous