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 conversionlong 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.