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.c
Replay: real traced execution (multi-file project)
#include <stdio.h>

int main(void) {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
    size_t n = sizeof(arr) / sizeof(arr[0]);
    int total = 0;
    for (size_t i = 0; i < n; ++i) {
        total = total + arr[i];
    }
    printf("%d\n", total);
    return 0;
}

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

    3int main(void) {4    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};5    size_t n = sizeof(arr) / sizeof(arr[0]);
    values this step[3, 1, 4, 1, 5, 9, 2, 6]arr

  2. n ← 8

    4int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};5size_t n = sizeof(arr) / sizeof(arr[0]);6int total = 0;
    values this step8n[3, 1, 4, 1, 5, 9, 2, 6]arr

  3. total ← 0

    5size_t n = sizeof(arr) / sizeof(arr[0]);6int total = 0;7for (size_t i = 0; i < n; ++i) {
    values this step0total8n

  4. total ← 3

    7for (size_t i = 0; i < n; ++i) {8    total = total + arr[i];9}
    values this step0 → 3total0i3arr[i]

  5. total ← 4

    7for (size_t i = 0; i < n; ++i) {8    total = total + arr[i];9}
    values this step3 → 4total1i1arr[i]

  6. total ← 8

    7for (size_t i = 0; i < n; ++i) {8    total = total + arr[i];9}
    values this step4 → 8total2i4arr[i]

  7. total ← 9

    7for (size_t i = 0; i < n; ++i) {8    total = total + arr[i];9}
    values this step8 → 9total3i1arr[i]

  8. total ← 14

    7for (size_t i = 0; i < n; ++i) {8    total = total + arr[i];9}
    values this step9 → 14total4i5arr[i]

  9. total ← 23

    7for (size_t i = 0; i < n; ++i) {8    total = total + arr[i];9}
    values this step14 → 23total5i9arr[i]

  10. total ← 25

    7for (size_t i = 0; i < n; ++i) {8    total = total + arr[i];9}
    values this step23 → 25total6i2arr[i]

  11. total ← 31

    7for (size_t i = 0; i < n; ++i) {8    total = total + arr[i];9}
    values this step25 → 31total7i6arr[i]

Trace Output

trace.c
Replay: real traced execution (multi-file project)
#include <stdio.h>

int main(void) {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
    size_t n = sizeof(arr) / sizeof(arr[0]);
    int total = 0;
    for (size_t i = 0; i < n; ++i) {
        int before = total;
        total = total + arr[i];
        printf("step %zu: arr[%zu]=%d total %d -> %d\n",
               i, i, arr[i], before, total);
    }
    printf("final total = %d\n", total);
    return 0;
}

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

    8int before = total;9total = total + arr[i];10printf("step %zu: arr[%zu]=%d total %d -> %d\n",
    values this step3totalstep 0: arr[0]=3 total 0 -> 3stdout0before3arr[i]

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

    8int before = total;9total = total + arr[i];10printf("step %zu: arr[%zu]=%d total %d -> %d\n",
    values this step4totalstep 1: arr[1]=1 total 3 -> 4stdout3before1arr[i]

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

    8int before = total;9total = total + arr[i];10printf("step %zu: arr[%zu]=%d total %d -> %d\n",
    values this step8totalstep 2: arr[2]=4 total 4 -> 8stdout4before4arr[i]

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

    8int before = total;9total = total + arr[i];10printf("step %zu: arr[%zu]=%d total %d -> %d\n",
    values this step9totalstep 3: arr[3]=1 total 8 -> 9stdout8before1arr[i]

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

    8int before = total;9total = total + arr[i];10printf("step %zu: arr[%zu]=%d total %d -> %d\n",
    values this step14totalstep 4: arr[4]=5 total 9 -> 14stdout9before5arr[i]

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

    8int before = total;9total = total + arr[i];10printf("step %zu: arr[%zu]=%d total %d -> %d\n",
    values this step23totalstep 5: arr[5]=9 total 14 -> 23stdout14before9arr[i]

  7. total ← 25, stdout ← step 6: arr[6]=2 total 23 -> 25

    8int before = total;9total = total + arr[i];10printf("step %zu: arr[%zu]=%d total %d -> %d\n",
    values this step25totalstep 6: arr[6]=2 total 23 -> 25stdout23before2arr[i]

  8. total ← 31, stdout ← step 7: arr[7]=6 total 25 -> 31

    8int before = total;9total = total + arr[i];10printf("step %zu: arr[%zu]=%d total %d -> %d\n",
    values this step31totalstep 7: arr[7]=6 total 25 -> 31stdout25before6arr[i]

  9. stdout ← final total = 31

    12}13printf("final total = %d\n", total);14return 0;
    values this stepfinal total = 31stdout31total

Complexity

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

Implementation notes

  • C: use the explicit for (size_t i = 0; i < n; ++i) loop with int total. There is no built-in sum() helper in C — the lesson is taught directly with the running accumulator.
  • int arr[] plus size_t n = sizeof(arr) / sizeof(arr[0]); documents the integer-array contract without hiding the iteration; size_t matches the size discipline sizeof returns.
  • The replay shows i, arr[i], and total before and after each addition, matching the lesson spec's state-transition table.