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

Trace Output

basic.go 
package main

import "fmt"

func main() {
	arr := []int{3, 1, 4, 1, 5, 9, 2, 6}
	total := 0
	for i := 0; i < len(arr); i++ {
		total = total + arr[i]
	}
	fmt.Println(total)
}
trace.go 
package main

import "fmt"

func main() {
	arr := []int{3, 1, 4, 1, 5, 9, 2, 6}
	total := 0
	for i := 0; i < len(arr); i++ {
		before := total
		total = total + arr[i]
		fmt.Printf("step %d: arr[%d]=%d total %d -> %d\n",
			i, i, arr[i], before, total)
	}
	fmt.Printf("final total = %d\n", total)
}

Complexity

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

Implementation notes

  • Go: use the explicit for i := 0; i < len(arr); i++ loop with total := 0. The range form is fine but the index form keeps i visible the way the lesson spec teaches it.
  • arr := []int{...} documents the integer-slice contract; len(arr) 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.