Arrays and Iteration

Array Sum (Linear Scan)

Walk an array once, accumulating each element into a running total. This is the canonical single-pass linear scan and the simplest possible loop invariant: after step i, total equals the sum of arr[0..i].

Algorithm

The canonical input from the lesson spec is arr = [3, 1, 4, 1, 5, 9, 2, 6]. After eight passes the running total is 31.

linear scan Visit each element exactly once in index order.
running total `total` accumulates the sum as the loop advances.

Basic Implementation

Basic.java
Replay: real traced execution (multi-file project)
public class Basic {
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
        int total = 0;
        for (int i = 0; i < arr.length; i++) {
            total = total + arr[i];
        }
        System.out.println(total);
    }
}

  1. arr ← [3, 1, 4, 1, 5, 9, 2, 6]

    2public static void main(String[] args) {3    int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};4    int total = 0;
    values this step[3, 1, 4, 1, 5, 9, 2, 6]arr

  2. total ← 0

    3int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};4int total = 0;5for (int i = 0; i < arr.length; i++) {
    values this step0total[3, 1, 4, 1, 5, 9, 2, 6]arr

  3. total ← 3

    5for (int i = 0; i < arr.length; i++) {6    total = total + arr[i];7}
    values this step0 → 3total0i3arr[i]

  4. total ← 4

    5for (int i = 0; i < arr.length; i++) {6    total = total + arr[i];7}
    values this step3 → 4total1i1arr[i]

  5. total ← 8

    5for (int i = 0; i < arr.length; i++) {6    total = total + arr[i];7}
    values this step4 → 8total2i4arr[i]

  6. total ← 9

    5for (int i = 0; i < arr.length; i++) {6    total = total + arr[i];7}
    values this step8 → 9total3i1arr[i]

  7. total ← 14

    5for (int i = 0; i < arr.length; i++) {6    total = total + arr[i];7}
    values this step9 → 14total4i5arr[i]

  8. total ← 23

    5for (int i = 0; i < arr.length; i++) {6    total = total + arr[i];7}
    values this step14 → 23total5i9arr[i]

  9. total ← 25

    5for (int i = 0; i < arr.length; i++) {6    total = total + arr[i];7}
    values this step23 → 25total6i2arr[i]

  10. total ← 31

    5for (int i = 0; i < arr.length; i++) {6    total = total + arr[i];7}
    values this step25 → 31total7i6arr[i]

Trace Output

Trace.java
Replay: real traced execution (multi-file project)
public class Trace {
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
        int total = 0;
        for (int i = 0; i < arr.length; i++) {
            int before = total;
            total = total + arr[i];
            System.out.println("step " + i + ": arr[" + i + "]=" + arr[i]
                + " total " + before + " -> " + total);
        }
        System.out.println("final total = " + total);
    }
}

  1. arr ← [3, 1, 4, 1, 5, 9, 2, 6]

    2public static void main(String[] args) {3    int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};4    int total = 0;
    values this step[3, 1, 4, 1, 5, 9, 2, 6]arr

  2. total ← 0

    3int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};4int total = 0;5for (int i = 0; i < arr.length; i++) {
    values this step0total[3, 1, 4, 1, 5, 9, 2, 6]arr

  3. stdout ← step 0: arr[0]=3 total 0 -> 3

    7total = total + arr[i];8System.out.println("step " + i + ": arr[" + i + "]=" + arr[i]9    + " total " + before + " -> " + total);
    values this stepstep 0: arr[0]=3 total 0 -> 3stdout0i

  4. stdout ← step 1: arr[1]=1 total 3 -> 4

    7total = total + arr[i];8System.out.println("step " + i + ": arr[" + i + "]=" + arr[i]9    + " total " + before + " -> " + total);
    values this stepstep 1: arr[1]=1 total 3 -> 4stdout1i

  5. stdout ← step 2: arr[2]=4 total 4 -> 8

    7total = total + arr[i];8System.out.println("step " + i + ": arr[" + i + "]=" + arr[i]9    + " total " + before + " -> " + total);
    values this stepstep 2: arr[2]=4 total 4 -> 8stdout2i

  6. stdout ← step 3: arr[3]=1 total 8 -> 9

    7total = total + arr[i];8System.out.println("step " + i + ": arr[" + i + "]=" + arr[i]9    + " total " + before + " -> " + total);
    values this stepstep 3: arr[3]=1 total 8 -> 9stdout3i

  7. stdout ← step 4: arr[4]=5 total 9 -> 14

    7total = total + arr[i];8System.out.println("step " + i + ": arr[" + i + "]=" + arr[i]9    + " total " + before + " -> " + total);
    values this stepstep 4: arr[4]=5 total 9 -> 14stdout4i

  8. stdout ← step 5: arr[5]=9 total 14 -> 23

    7total = total + arr[i];8System.out.println("step " + i + ": arr[" + i + "]=" + arr[i]9    + " total " + before + " -> " + total);
    values this stepstep 5: arr[5]=9 total 14 -> 23stdout5i

  9. stdout ← final total = 31

    10    }11    System.out.println("final total = " + total);12}
    values this stepfinal total = 31stdout31total

Complexity

  • Time: O(n)
  • Space: O(1)

Implementation notes

  • Java: use the explicit for (int i = 0; i < arr.length; i++) loop and int total. Calling Arrays.stream(arr).sum() would hide the iteration the lesson is teaching.
  • The replay shows i, arr[i], and total before and after each addition, matching the lesson spec's state-transition table.