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.rs

fn main() {
	let arr = [3, 1, 4, 1, 5, 9, 2, 6];
	let mut total = 0;
	for i in 0..arr.len() {
		total = total + arr[i];
	}
	println!("{}", total);
}

trace.rs

fn main() {
	let arr = [3, 1, 4, 1, 5, 9, 2, 6];
	let mut total = 0;
	for i in 0..arr.len() {
		let before = total;
		total = total + arr[i];
		println!("step {}: arr[{}]={} total {} -> {}",
			i, i, arr[i], before, total);
	}
	println!("final total = {}", total);
}

Complexity

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

Implementation notes

Rust: use the explicit for i in 0..arr.len() loop with let mut total = 0;. The iterator form arr.iter().sum() is fine for production but hides the loop the lesson spec is teaching.
let arr = [3, 1, 4, 1, 5, 9, 2, 6]; documents the fixed-size [i32; 8] array contract; arr.len() gives the explicit count without leaning on a helper that hides the iteration.
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.