Sums, swaps, minimums, and counts

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.

Swap two slots via a temporary variable (three-statement idiom)

To exchange the values at two array positions, the canonical Java pattern is three statements:

final int temp = xs[i];
xs[i]          = xs[j];
xs[j]          = temp;

The temporary preserves the original value of xs[i] so that overwriting xs[i] does not lose it. Every sort algorithm in concept areas 10 and 11 uses this exact idiom; recognizing it instantly is part of reading sort code.

Why the temp is necessary

Without the temp, the two-statement attempt destroys data:

xs[i] = xs[j];        // step 1: xs[i] now holds xs[j]'s old value: and xs[i]'s old value is gone
xs[j] = xs[i];        // step 2: xs[j] = xs[i] = xs[j]'s old value (no change!)

After the two lines, xs[i] and xs[j] both hold xs[j]'s original value. xs[i]'s original value has been overwritten and is unrecoverable. The bug is silent: the program produces wrong output without crashing. The temp is exactly the save-before-overwrite step that the two-statement form omits.

Why not the "XOR trick"

C and C++ folklore promotes a no-temp swap:

xs[i] ^= xs[j];
xs[j] ^= xs[i];
xs[i] ^= xs[j];

This works for distinct integer slots (it relies on a ^ b ^ b = a), but breaks when i == j (both slots become 0) and does not work for double or String arrays. The temp idiom is universal across element types, costs one local variable, and is the form every JDK sort routine uses. Use the temp.

A common variation: swap(xs, i, j) as a helper method

Selection sort and insertion sort each invoke a swap multiple times; the three-statement form is often extracted into a small helper:

public static void swap(final int[] xs, final int i, final int j) {
    final int temp = xs[i];
    xs[i] = xs[j];
    xs[j] = temp;
}

The helper makes the calling sort algorithm read at a higher level: if (xs[a] > xs[b]) swap(xs, a, b); rather than three lines inline. The same idea appears in the static helper method pattern.

Reach for the library first (for List)

For an ArrayList<E> or any List<E>, the JDK already ships the helper: java.util.Collections.swap(List<?>, int, int). The CSCD 210 lab style writes the three-statement form by hand because the labs use primitive int[]/double[]/char[] arrays, which have no built-in swap method. For list-based data, reach for Collections.swap first: the JDK implementation is the same three-line idiom, but importing the library signals to the reader that the swap is library-vetted.

In other languages

• Python: xs[i], xs[j] = xs[j], xs[i]: the tuple-pack/unpack idiom. No temp needed, no bug. Python's evaluation rule (right-hand side fully evaluated first) makes the swap atomic.
• C: identical three-statement form; identical reasoning. No tuple swap.
• JavaScript: identical three-statement form. ES6 added [a, b] = [b, a] destructuring, analogous to Python.
• Rust: xs.swap(i, j) is a method on slices. The two-statement attempt fails the borrow checker, which is the language's way of refusing to compile the bug.

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.

Counting elements that match a condition

The counting pattern: declare a counter starting at zero, increment it for every element that satisfies a predicate, return the counter. The skeleton is identical to the sum pattern, but the body adds 1 per match instead of adding the element's value.

public static int countEvens(final int[] xs) {
    int count = 0;
    for (int v : xs) {
        if (v % 2 == 0) {
            count++;
        }
    }
    return count;
}

public static int countAbove(final int[] xs, final int threshold) {
    int count = 0;
    for (int v : xs) {
        if (v > threshold) {
            count++;
        }
    }
    return count;
}

The condition lives in the if body. The ++ happens only when the condition is true. There is no shorter form in CSCD 210 idiom; (count += (v > threshold ? 1 : 0) exists but is harder to read and not used in lab style).

The shape generalizes

Three accumulator-family patterns share the same skeleton:

| Pattern | What you start with | What the body adds | |---------|---------------------|--------------------| | Sum | int total = 0 | v (the element) | | Count | int count = 0 | 1 (only if condition holds) | | Average | int total = 0 | v, then divide by xs.length after |

Min and max are different: the body replaces the accumulator rather than adding to it. The mental model "accumulator pattern" covers sum, count, average; "best-so-far pattern" covers min, max.

When the condition uses the index

If the condition depends on position (e.g., "count elements at even indices"), the enhanced-for cannot help: the loop variable is the value, not the index. Use a traditional for:

public static int countEvenIndices(final int[] xs) {
    int count = 0;
    for (int i = 0; i < xs.length; i++) {
        if (i % 2 == 0) {
            count++;
        }
    }
    return count;
}

This is one of the canonical cases where the enhanced-for does not fit, by the three-condition fit test.

In other languages

• Python: sum(1 for v in xs if v > threshold) is the one-liner; [v for v in xs if v > threshold].count() (longer) also works.
• C: identical loop pattern; no list-comprehension shortcut.
• Java streams: Arrays.stream(xs).filter(v -> v > threshold).count(); out of scope for CSCD 210.