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

object Main {
	def main(args: Array[String]): Unit = {
		val arr = Array(3, 1, 4, 1, 5, 9, 2, 6)
		var total = 0
		for (i <- arr.indices) {
			total = total + arr(i)
		}
		println(total)
	}
}

trace.scala

object Main {
	def main(args: Array[String]): Unit = {
		val arr = Array(3, 1, 4, 1, 5, 9, 2, 6)
		var total = 0
		for (i <- arr.indices) {
			val before = total
			total = total + arr(i)
			println(s"step $i: arr($i)=${arr(i)} total $before -> $total")
		}
		println(s"final total = $total")
	}
}

Complexity

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

Implementation notes

Scala: use the explicit for (i <- arr.indices) loop with var total = 0. The stdlib arr.sum is fine for production but hides the loop the lesson spec is teaching.
val arr = Array(3, 1, 4, 1, 5, 9, 2, 6) documents the fixed-size array contract; arr.indices gives the explicit index range 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.