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

The canonical input from the lesson spec is $arr = [3, 1, 4, 1, 5, 9, 2, 6]. After eight passes the running total is 31.

linear scan Visit each element exactly once in index order.
running total `total` accumulates the sum as the loop advances.

Basic Implementation

basic.php
Replay: real traced execution (multi-file project)
<?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";

  1. $arr ← [3, 1, 4, 1, 5, 9, 2, 6]

    1<?php2$arr = [3, 1, 4, 1, 5, 9, 2, 6];3$total = 0;
    values this step[3, 1, 4, 1, 5, 9, 2, 6]$arr

  2. $total ← 0

    2$arr = [3, 1, 4, 1, 5, 9, 2, 6];3$total = 0;4$i = 0;
    values this step0$total[3, 1, 4, 1, 5, 9, 2, 6]$arr

  3. $total ← 3

    5while ($i < count($arr)) {6	$total = $total + $arr[$i];7	$i = $i + 1;
    values this step0 → 3$total0$i3$arr[$i]

  4. $total ← 4

    5while ($i < count($arr)) {6	$total = $total + $arr[$i];7	$i = $i + 1;
    values this step3 → 4$total1$i1$arr[$i]

  5. $total ← 8

    5while ($i < count($arr)) {6	$total = $total + $arr[$i];7	$i = $i + 1;
    values this step4 → 8$total2$i4$arr[$i]

  6. $total ← 9

    5while ($i < count($arr)) {6	$total = $total + $arr[$i];7	$i = $i + 1;
    values this step8 → 9$total3$i1$arr[$i]

  7. $total ← 14

    5while ($i < count($arr)) {6	$total = $total + $arr[$i];7	$i = $i + 1;
    values this step9 → 14$total4$i5$arr[$i]

  8. $total ← 23

    5while ($i < count($arr)) {6	$total = $total + $arr[$i];7	$i = $i + 1;
    values this step14 → 23$total5$i9$arr[$i]

  9. $total ← 25

    5while ($i < count($arr)) {6	$total = $total + $arr[$i];7	$i = $i + 1;
    values this step23 → 25$total6$i2$arr[$i]

  10. $total ← 31

    5while ($i < count($arr)) {6	$total = $total + $arr[$i];7	$i = $i + 1;
    values this step25 → 31$total7$i6$arr[$i]

Trace Output

trace.php
Replay: real traced execution (multi-file project)
<?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";

  1. $total ← 3, stdout ← step 0: arr(0)=3 total 0 -> 3

    6$before = $total;7$total = $total + $arr[$i];8echo "step $i: arr($i)={$arr[$i]} total $before -> $total\n";
    values this step3$totalstep 0: arr(0)=3 total 0 -> 3stdout0$before3$arr[$i]

  2. $total ← 4, stdout ← step 1: arr(1)=1 total 3 -> 4

    6$before = $total;7$total = $total + $arr[$i];8echo "step $i: arr($i)={$arr[$i]} total $before -> $total\n";
    values this step4$totalstep 1: arr(1)=1 total 3 -> 4stdout3$before1$arr[$i]

  3. $total ← 8, stdout ← step 2: arr(2)=4 total 4 -> 8

    6$before = $total;7$total = $total + $arr[$i];8echo "step $i: arr($i)={$arr[$i]} total $before -> $total\n";
    values this step8$totalstep 2: arr(2)=4 total 4 -> 8stdout4$before4$arr[$i]

  4. $total ← 9, stdout ← step 3: arr(3)=1 total 8 -> 9

    6$before = $total;7$total = $total + $arr[$i];8echo "step $i: arr($i)={$arr[$i]} total $before -> $total\n";
    values this step9$totalstep 3: arr(3)=1 total 8 -> 9stdout8$before1$arr[$i]

  5. $total ← 14, stdout ← step 4: arr(4)=5 total 9 -> 14

    6$before = $total;7$total = $total + $arr[$i];8echo "step $i: arr($i)={$arr[$i]} total $before -> $total\n";
    values this step14$totalstep 4: arr(4)=5 total 9 -> 14stdout9$before5$arr[$i]

  6. $total ← 23, stdout ← step 5: arr(5)=9 total 14 -> 23

    6$before = $total;7$total = $total + $arr[$i];8echo "step $i: arr($i)={$arr[$i]} total $before -> $total\n";
    values this step23$totalstep 5: arr(5)=9 total 14 -> 23stdout14$before9$arr[$i]

  7. $total ← 25, stdout ← step 6: arr(6)=2 total 23 -> 25

    6$before = $total;7$total = $total + $arr[$i];8echo "step $i: arr($i)={$arr[$i]} total $before -> $total\n";
    values this step25$totalstep 6: arr(6)=2 total 23 -> 25stdout23$before2$arr[$i]

  8. $total ← 31, stdout ← step 7: arr(7)=6 total 25 -> 31

    6$before = $total;7$total = $total + $arr[$i];8echo "step $i: arr($i)={$arr[$i]} total $before -> $total\n";
    values this step31$totalstep 7: arr(7)=6 total 25 -> 31stdout25$before6$arr[$i]

  9. stdout ← final total = 31

    10}11echo "final total = $total\n";
    values this stepfinal total = 31stdout31$total

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.