Sums, averages, minimums, and maximums

Sum and average over an array

The accumulator pattern: declare a running total before the loop, add each element to it inside the loop, return the total (or divide by length to get the average) after the loop. This is the first composite loop pattern students see, and it underlies count, max, min, and most other reductions.

public static int sum(final int[] xs) {
    int total = 0;
    for (int v : xs) {
        total += v;
    }
    return total;
}

public static double average(final int[] xs) {
    return (double) sum(xs) / xs.length;
}

Three commitments are visible in this shape:

1. The accumulator starts at the identity element. For sum, the identity is 0: adding it changes nothing. For product, the identity is 1. For min, the identity is Integer.MAX_VALUE. Choosing the right starting value matters, and the best-so-far pattern for min and max revisits this. 2. The loop body's only effect is to update the accumulator. No System.out.println, no array writes, no early return. The body is one operation per slot. 3. The accumulator is the answer. The method returns it directly. No second pass is needed.

The enhanced-for is the natural choice here (the body uses only the value, never the index). The traditional for is identical in behavior: pick the form that reads cleanly.

Average is not sum / length with integer arithmetic

return sum(xs) / xs.length;        //  BUG: integer division

If sum returns int and xs.length is int, the / is integer division, which truncates toward zero. For an array of three values {1, 1, 2}, the sum is 4, the length is 3, and 4 / 3 is 1, not 1.333…. The fix is to promote at least one operand to double:

return (double) sum(xs) / xs.length;   //  promote the dividend; quotient is 1.333…
return sum(xs) / (double) xs.length;   //  promote the divisor; same result
return (sum(xs) * 1.0) / xs.length;    //  multiplication promotes; works but ugly

The cast on the dividend is the conventional form.

Overflow on int accumulators

For a large array of int values, the sum can exceed Integer.MAX_VALUE (2 147 483 647) and wrap around silently to a negative number. This rarely matters for CSCD 210 lab data (small arrays of small values) but is a real production concern. The fix is to declare the accumulator as long:

long total = 0L;
for (int v : xs) total += v;
return total;

For double arrays the analogous concern is loss of precision when summing many small values together; the textbook discusses this only briefly (BJP.p269) and CSCD 210 does not assess it.

In other languages

• Python: sum(xs) is a built-in; statistics.mean(xs) returns the average. Both handle integer division automatically because Python's / is always floating-point.
• C: identical accumulator pattern; the same overflow risk on int accumulators. long long is the C equivalent of Java's long.
• Java streams: IntStream.of(xs).sum() and IntStream.of(xs).average() exist; out of scope for CSCD 210.

Min and max over an array

A close relative of the accumulator pattern: declare a best-so-far variable before the loop, replace it whenever the loop sees a better candidate, return it after. The body's only operation is the comparison-and-replace.

public static int min(final int[] xs) {
    int best = xs[0];                       // seed with first element
    for (int i = 1; i < xs.length; i++) {   // start at index 1, since 0 is the seed
        if (xs[i] < best) {
            best = xs[i];
        }
    }
    return best;
}

Two implementation choices distinguish good code from buggy code:

1. Seed from xs[0], not from Integer.MAX_VALUE. The "magic seed" approach (int best = Integer.MAX_VALUE;) is a common alternative but introduces a subtle bug: if the input array is empty, the method returns Integer.MAX_VALUE, which is a meaningful integer value, not an obvious error. The xs[0] seed throws ArrayIndexOutOfBoundsException on the empty input, which is a louder failure, but it should be replaced by an explicit IllegalArgumentException precondition check. Either way, the empty-array case must be handled. 2. Start the loop at index 1, not 0. Comparing xs[0] against itself (if (xs[0] < best)) is harmless but wasteful and looks like the code does not know what best was initialized to. The convention for (int i = 1; i < xs.length; i++) skips the redundant check and signals that xs[0] has already been considered.

The same shape works for max with the comparison flipped:

public static int max(final int[] xs) {
    int best = xs[0];
    for (int i = 1; i < xs.length; i++) {
        if (xs[i] > best) {
            best = xs[i];
        }
    }
    return best;
}

Finding the index of the minimum

A variation: return the index of the minimum, not the value. This is what selection sort uses.

public static int indexOfMin(final int[] xs) {
    int bestIdx = 0;
    for (int i = 1; i < xs.length; i++) {
        if (xs[i] < xs[bestIdx]) {
            bestIdx = i;
        }
    }
    return bestIdx;
}

The comparison now reads xs[i] < xs[bestIdx] (two array reads per iteration) instead of xs[i] < best (one array read, one variable read). The pattern is otherwise identical.

In other languages

• Python: min(xs) and max(xs) are built-ins. xs.index(min(xs)) is the idiomatic "index of min" (less efficient, two passes).
• C: identical accumulator pattern; no built-in min for arrays: the loop is the answer.
• Java streams: IntStream.of(xs).min().getAsInt() exists; out of scope for CSCD 210.