TCHS-7-500

 

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.

import java.util.Arrays;

public class StraightArray {

	public int howManyMore(int[] nums) {
		Arrays.sort(nums);
		int min = 4;
		for (int i = 0; i < nums.length; i++) {
			int c = 4;
			for (int j = 1; j < 5; j++)
				if (Arrays.binarySearch(nums, nums[i] + j) > -1)
					c--;
			min = Math.min(min, c);
		}
		return min;
	}

}