I needed to test whether a set of integers, T, formed a consecutive series including all integers from min(T) to max(T).

This can be achieved by sorting T into ascending order and, for each index i, checking whether T[i] is one larger than its predecessor, T[i-1]:

public static boolean cons_sort(List<Integer> T) {
Collections.sort(T);

for (int i = 1; i < T.size(); i++)
if (T.get(i – 1) + 1 != T.get(i))
return false;

return true;
}

Sorting costs O(n log n). However it is not necessary to sort the numbers. Using the result of Gauss that the sum of a consecutive series of integers, T, must equal (max(T) + min(T)) * (max(T) – min(T) + 1) / 2 a speed up can be achieved.

public static boolean cons_gauss(List<Integer> T) {

Set<Integer> Tset = new HashSet<Integer>(T);

if(Tset.size() < T.size())
return false; // duplicate found; was eliminated in set conversion

long sum = 0, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;

for (int t : Tset) {

sum = sum + t;

if (t < min)
min = t;
if (t > max)
max = t;
}

return (max + min) * (max – min + 1) / 2 == sum;
}

I performed some tests on Java 1.6 update 3 using this testbench:

public static void main(String[] args) {

List<Long> SortResults = new ArrayList<Long>(), GaussResults = new ArrayList<Long>();

for (int i = 0; i < runs; i++) {
List<Integer> T = getConsecutiveIntArray();

if (i % 2 == 0) {
} else {
}
}

System.out.printf(“Gauss: t %f (%f)nSort: t %f (%f)nRatio:t%f”,
mean(GaussResults), std(GaussResults), mean(SortResults),
std(SortResults), mean(SortResults) / mean(GaussResults));
}

Where the getConsecutiveIntArray is defined as:

public static List<Integer> getConsecutiveIntArray() {
List<Integer> T = new ArrayList<Integer>(N);

for (int i = 0; i < N; i++)