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.php 
<?php
$arr = [3, 1, 4, 1, 5, 9, 2, 6];
$total = 0;
$i = 0;
while ($i < count($arr)) {
	$total = $total + $arr[$i];
	$i = $i + 1;
}
echo $total . "\n";
trace.php 
<?php
$arr = [3, 1, 4, 1, 5, 9, 2, 6];
$total = 0;
$i = 0;
while ($i < count($arr)) {
	$before = $total;
	$total = $total + $arr[$i];
	echo "step $i: arr($i)={$arr[$i]} total $before -> $total\n";
	$i = $i + 1;
}
echo "final total = $total\n";

Complexity

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

Implementation notes

  • PHP: use the explicit while ($i < count($arr)) loop with $total = 0 and a manual index. The stdlib array_sum($arr) is fine for production but hides the loop the lesson spec is teaching.
  • $arr = [3, 1, 4, 1, 5, 9, 2, 6] documents the fixed-content array; the manual $i = $i + 1 step keeps the iteration without leaning on foreach or array_reduce that hide the running update.
  • 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.