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) {
SortResults.add(timeMethod(Method.sort, T));
GaussResults.add(timeMethod(Method.gauss, T));
} else {
GaussResults.add(timeMethod(Method.gauss, T));
SortResults.add(timeMethod(Method.sort, T));
}
}

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++)
T.add(i);

Collections.shuffle(T);

return T;
}

With runs = 100 and N = 500000, Gauss is about 1,8 times faster than sorting. With runs = 10 and N = 1000000 Gauss leads by a factor of 2,4 and seems more stable wrt running time. Setting runs = 100000 and N = 100 gives a ratio of 1,6 and decreasing N will bring gauss and sorting closer and closer.

The sorting approach has an advantage because it may return early in case it finds a hole in the number series. But it is still necessary for it to sort the list entirely - in O(n log n) - whereas Gauss always scans the entire list but this costs only O(n).

Feel free to browse the entire java source.

Update 04-12-2007: in a comment by Alonso Ulloa the need to check the integer array for duplicates became evident. I have re-written the code and reflected the changes in this article. Performance wise the new approach reduces the gap between sorting and gauss significantly, but gauss still performs better.