Array scans and what the accumulator means

Visiting elements without losing the state

An array trace records each element. A loop lets us visit several positions in order, but the old rules still apply: use the current state, check the selected index and record each update where it happens.

In this lesson you will explain which prefix of an array has been processed, distinguish an index from a count or total, and find the first matching position without overwriting it with a later match. You will also handle a chosen empty prefix safely.

Prerequisites: the accepted lessons on conditions, short circuit, finite loops, accumulators and current-state tracing, plus the previous lesson on array elements and valid indices. No pointers, early-exit statements or formal complexity notation are needed.

We use C11 as our teaching convention. Arrays have explicit positive constant sizes and initialized int elements. A separate length selects how many elements from the beginning we will process. It must be between zero and the actual element count, inclusive. All integer calculations shown fit within −32767 through 32767. Each complete program is independent; do not join them together. Incorrect boundary conditions discussed in prose are for reasoning only, not execution.

Capacity, selected length and the next index

For int readings[5] = {3, 8, 0, 6, 2};, the array has five elements at indices 0 through 4. In this lesson, capacity means this actual element count. It is not a byte count.

A chosen length of 3 means process indices 0, 1 and 2. That beginning part is a prefix. The elements at indices 3 and 4 still exist, but they are outside the selected prefix. A length of 5 selects the whole array. A length of 0 selects no elements; it does not declare a zero-length C array or remove the existing storage.

For a forward scan, start i at 0 and use i < length. Just before a test, i is the next candidate index. When the test is true, the body may access that position. After the loop's i++ update stage, the next test uses the new index. This update happens after the body; it is not an extra statement hidden inside the body.

Do not read readings[length] as the final selected element. For a nonempty prefix, its final element is at length - 1. When length is zero, there is no final selected element at all. Our scans handle that case by executing no bodies, without trying to calculate and access index −1.

Worked example 1 Count selected values and total them

We want the count and sum of readings that are at least 5. The index, the count and the total have different jobs. Predict the output, then explain the meaning of each accumulator.

#include <stdio.h>

int main(void)
{
    int readings[5] = {3, 8, 0, 6, 2};
    int length = 5;
    int count = 0;
    int total = 0;
    for (int i = 0; i < length; i++) {
        if (readings[i] >= 5) {
            count++;
            total += readings[i];
        }
    }
    printf("%d %d\n", count, total);
    return 0;
}

Trace the state immediately after each body:

After the last body, the update makes the loop's i equal to 5. The test 5 < 5 is false, so no access at index 5 occurs. The output is 2 14, followed by a newline. The array itself is unchanged: the body reads its elements and writes only the accumulators.

The loop has five bodies, five updates and six loop-condition tests, including the final failed test. Its inner if condition is evaluated five times. The two selected inner branches update count and total twice. A loop body and a selected inner branch are not the same event.

Say what an accumulator means at a checkpoint

Choose the checkpoint just before each loop test. At that point:

• i elements of the chosen prefix have already been visited, at indices 0 through i - 1
• count is the number of those visited elements whose value is at least 5
• total is the sum of those qualifying visited values

When i is zero, there are no visited elements. Count 0 and total 0 are therefore the correct starting state. The phrase “0 through i - 1” describes an empty set at this point; it is not an instruction to access index −1.

If the test succeeds, inspect exactly the next element. When it qualifies, add one to the count and add its value to the total. When it does not, leave both unchanged. The update advances to the next index. Either way, the checkpoint description is true again at the next test. This is the loop invariant: a stable explanation of what the current variables represent.

When the test finally fails, i equals length, so the description covers the entire selected prefix. The starting value, progress by one and finite valid length also explain why the loop stops. With length = 0, the first test fails: zero bodies, one loop test, count 0 and total 0. The real five-element array still exists.

5 19 would count and add every reading, ignoring the inner condition. 2 2 would confuse the sum with the number of qualifying elements. Resetting total = 0 inside each body would discard earlier contributions. These are different mistakes, so the explanation must name what each variable is meant to retain.

Worked example 2 Keep the first matching position

A target can occur more than once. We will scan the whole chosen prefix while recording only its earliest matching index. The value −1 is our not-found marker because it is outside the valid element indices. It is a signal, never an index to read.

#include <stdio.h>

int main(void)
{
    int values[6] = {7, 2, 5, 2, 9, 2};
    int length = 6;
    int target = 2;
    int first = -1;
    for (int i = 0; i < length; i++) {
        if (first == -1 && values[i] == target) {
            first = i;
        }
    }
    printf("%d\n", first);
    return 0;
}

• Before visiting index 0: first = -1; no visited match exists
• At index 0, first == -1 is true, so compare value 7 with target 2. It does not match; first stays −1
• At index 1, no match has yet been recorded. Value 2 matches, so store the index: first = 1
• At indices 2, 3, 4 and 5, first == -1 is false. && skips the element comparison, the assignment is skipped, and first stays 1
• The update after index 5 prepares index 6; the loop test fails. Output: 1, followed by a newline

The variable stores a position, not the target value. The answer is 1, not 2. The later matching positions 3 and 5 do not replace the saved position. The first == -1 guard protects the first result from being overwritten; it does not stop the loop. There are still six bodies and seven loop tests. The comparison values[i] == target is evaluated only at indices 0 and 1 in this run.

At the test checkpoint, first has one of two meanings: −1 if no visited element matches, or the smallest matching index among the positions already visited. A newly encountered match is recorded only while the marker is still −1. Once a first match exists, preserving it is correct even if later positions also match.

If no chosen element matches, the marker remains −1. If the chosen length is zero, no positions are visited and it also remains −1. Neither case permits reading values[first]. Test whether a match was found before using the recorded position. In the programs here, if (first != -1) is sufficient because our algorithm produces only −1 or a valid selected index; that is not a general validation rule for an arbitrary integer supplied by someone else.

Define the contract before the loop

Every scan here assumes initialized storage and 0 <= length <= capacity. The loop condition enforces the selected upper boundary only when that contract is already true. Giving a five-element array length = 8 does not grow it, and i < length cannot protect against that incorrect length.

The sum examples also assume that every intermediate addition fits in int. Small examples satisfy this explicitly; a loop pattern is not a promise that any length or values will be safe. We count source-level steps to understand the code, without claiming a particular machine running time or covering formal algorithm complexity.

Practice before the solutions

These four original learning exercises are unscored. Record the state that explains your answer. Do not execute a proposed bad boundary condition to discover whether it happens to print a number.

Practice 1 Accumulate the updated elements

Give the final array and output. Does total accumulate the original values or the values after their updates?

#include <stdio.h>

int main(void)
{
    int a[4] = {2, 5, 1, 4};
    int total = 0;
    for (int i = 0; i < 4; i++) {
        a[i] = a[i] + i;
        total += a[i];
    }
    printf("%d %d %d\n", total, a[1], a[3]);
    return 0;
}

Practice 2 An empty selected prefix

Count the bodies and loop tests, and give the output. Is changing i < length to i <= length a correct condition for every allowed length from 0 through 3?

#include <stdio.h>

int main(void)
{
    int values[3] = {6, 1, 9};
    int length = 0;
    int count = 0;
    int total = 0;
    for (int i = 0; i < length; i++) {
        count++;
        total += values[i];
    }
    printf("%d %d %d\n", count, total, values[0]);
    return 0;
}

Practice 3 A name does not enforce first-match behavior

The program is defined, but does it find the first occurrence? Give its actual output. Then change only the inner condition so it retains the first matching position.

#include <stdio.h>

int main(void)
{
    int a[5] = {4, 7, 4, 1, 4};
    int first = -1;
    for (int i = 0; i < 5; i++) {
        if (a[i] == 4) {
            first = i;
        }
    }
    printf("%d\n", first);
    return 0;
}

Practice 4 Search only the chosen prefix

The full array contains 6. Explain why the program does or does not report it. Give the output and state whether the guarded element read occurs.

#include <stdio.h>

int main(void)
{
    int a[5] = {4, 8, 6, 8, 1};
    int length = 2;
    int target = 6;
    int first = -1;
    for (int i = 0; i < length; i++) {
        if (first == -1 && a[i] == target) {
            first = i;
        }
    }
    int matched_value = 0;
    if (first != -1) {
        matched_value = a[first];
    }
    printf("%d %d\n", first, matched_value);
    return 0;
}

Full solutions and wrong-turn feedback

Practice 1 solution

At index 0, store 2 + 0 = 2; add the updated 2, so total = 2. At index 1, store 5 + 1 = 6; the total becomes 8. At index 2, store 1 + 2 = 3; the total becomes 11. At index 3, store 4 + 3 = 7; the total becomes 18.

The final array is {2, 6, 3, 7}. After the final update the loop tests 4 < 4, which is false. There are four bodies and five loop tests. Output: 18 6 7, then a newline.

At each test, the visited prefix has been updated and total contains its updated values' sum. The unvisited suffix still has its original values. The statement order makes the difference: each new element value is stored before the addition reads that element.

A total of 12 adds only the original values. A total of 6 adds only the indices. Outputting 18 5 4 ignores the array's changes even though it correctly totals the updated values. A state record must account for both the stored array and the accumulator.

Practice 2 solution

Initialization sets i = 0. The first test is 0 < 0, which is false. There are zero bodies, zero updates and one loop test. Both accumulators remain zero. The later values[0] in printf is a separate, valid access to the real array's first element, whose value is still 6. Output: 0 0 6, then a newline.

An empty selected prefix does not make the whole array disappear or require a zero-length declaration. Conversely, the existence of the value 6 does not make a loop with a false first test execute once.

The proposed i <= length is wrong. At length 0, it would process index 0 even though no elements were selected. At length 3, it would eventually attempt index 3, outside this three-element array. That full-length case has undefined behavior; no numeric output is prescribed. Classify the bad boundary without running it. The correct count-to-index relationship needs the strict upper test.

Practice 3 solution

The matching positions are 0, 2 and 4. The assignment executes at each of them: first becomes 0, then 2, then 4. The intervening elements do not match, so they leave it unchanged. The program prints 4 followed by a newline: it retained the last matching index, despite the name first.

Use first == -1 && a[i] == 4 as the inner condition. A complete repaired program is:

#include <stdio.h>

int main(void)
{
    int a[5] = {4, 7, 4, 1, 4};
    int first = -1;
    for (int i = 0; i < 5; i++) {
        if (first == -1 && a[i] == 4) {
            first = i;
        }
    }
    printf("%d\n", first);
    return 0;
}

At index 0 the repaired condition records first = 0. Later bodies see that the marker is no longer −1 and leave it unchanged. The repaired output is 0, then a newline. Both versions still have five bodies and six loop tests; only the inner condition differs.

An answer of 4 for the repaired version forgets the new guard. Changing the initializer to 0 would not be a general repair: it would claim a match at index 0 before any comparison, even for a target absent from the array. Renaming the variable does not change execution either.

Practice 4 solution

Only positions 0 and 1 belong to the selected prefix. At index 0, value 4 does not equal 6, so first stays −1. At index 1, value 8 does not equal 6 either. After the update to index 2, 2 < 2 is false and the scan ends. It never compares the value at index 2.

The test first != -1 is false, so a[first] is not evaluated. matched_value keeps its explicitly initialized fallback 0. Output: -1 0, then a newline. The marker −1 carries the not-found information; the fallback 0 is only what this program chose to print alongside it, not a universal not-found element value.

2 6 searches beyond the selected prefix. -1 6 reads an unselected element despite the failed guard. A zero in matched_value alone would not distinguish a found element whose value is zero from no match; keep the position/marker test as part of the explanation.

Before moving on

Explain what each variable means before the next loop test, not just what it prints at the end. You should be able to distinguish an empty prefix, an absent target and a later duplicate match. The next lesson introduces a pointer's target and follows two routes to the same scalar object; it does not change the current-state method you have used here.

Source note

The explanations, programs, traces and exercises are original. C facts were checked against the WG14 N1570 C11 committee draft: indexed elements and bounds §§6.5.2.1p2, 6.5.6p8; for order §6.8.5.3p1; loop stopping §6.8.5p4; selected branches §6.8.4.1p2; short circuit §6.5.13p4; assignment and updates §§6.5.16.1p2, 6.5.16.2p3, 6.5.2.4p2. Reference: https://open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

C11 is this course's teaching convention. These scans introduce array reasoning and a simple search; they do not complete GATE searching, complexity or Programming and Data Structures.

Quick reference

• Capacity is the actual element count; length chooses a prefix from 0 through that capacity
• For a forward scan, i = 0; i < length; i++ visits exactly the selected positions
• Just before a test, explain the already visited prefix and what each accumulator contains
• A count records how many elements meet a rule; a total adds their values; an index names a position
• Initialize accumulators before the loop so earlier contributions are retained
• Length 0 means zero bodies and one initial failed test, not a zero-sized C array
• A first-match marker of −1 means no match yet; record an index only while the marker remains −1
• The first-match guard does not stop the loop; it prevents later overwrites
• Check that a match exists before using its index; never read an array at the −1 marker
• The chosen length must fit the real array; a loop condition cannot repair a false capacity claim