TopCoder problem "StraightArray" used in TCHS SRM 7 (Division I Level Two)



Problem Statement

    

An array of ints is said to be a straight if it contains five elements that are five consecutive numbers. For example, the array { 6, 1, 9, 5, 7, 15, 8 } is a straight because it contains 5, 6, 7, 8, and 9.

Given an array of ints, nums, return the minimum number of ints that must be added to that array, so that the augmented array is a straight.

 

Definition

    
Class:StraightArray
Method:howManyMore
Parameters:int[]
Returns:int
Method signature:int howManyMore(int[] nums)
(be sure your method is public)
    
 

Constraints

-nums contains between 1 and 50 elements, inclusive.
-Each element in nums is between 0 and 1,000,000,000, inclusive.
-All elements in nums are distinct.
 

Examples

0)
    
{ 5, 6, 7 }
Returns: 2
We can make a straight if we add the two numbers 8 and 9, so we return 2. (Note that we cannot make a straight by adding fewer than two numbers.)
1)
    
{ 5, 7, 9, 8492, 8493, 192398 }
Returns: 2
We can add the two numbers 6 and 8 to get a straight.
2)
    
{ 1000, 2000, 3000, 4000 }
Returns: 4
For example, we can add 1997, 1998, 1999, and 2001.
3)
    
{ 399710788, 908814160, 716153223, 970654133, 506644631, 217544361, 
  260957226, 132981872, 483739151, 595795986, 824140293, 362514681, 
  716153227, 336131843, 406529057, 147725164 } 
Returns: 3
We get a straight if we add 716153224, 716153225, and 716153226.
4)
    
{ 6, 1, 9, 5, 7, 15, 8 }
Returns: 0
From the problem statement. It already is a straight.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10059&pm=5997

Writer:

Googly

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Simple Search, Iteration