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

Trace Output

basic.c

#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;
}

trace.c

#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;
}

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.

linear scan Visit each element exactly once in index order.

running total `total` accumulates the sum as the loop advances.