Skip to content
ExamSpine

Lesson 5.8

Accumulate over a list

Part 5: Text, lists, stacks and queuesReading, about 5 min3 exercises in this lesson

Java answers can't run on Spine yet. You can still read Java, trace it, and put an answer's lines in order.

Walking a list once to search it or add it up

By the end of this you will be able to walk through a list once and either add something up as you go, or stop as soon as you find what you are looking for.

Many list tasks are one of two kinds. Accumulating needs every value before it can answer: how many, or the total. Searching looks for a value that passes a test, and can answer the moment it finds one. If you are not sure which you have, ask: could I know the answer before I have seen every value? Both use one loop over the list (an array in Java) and one variable that lives outside the loop, so it survives from one value to the next.

Accumulating: a total that starts before the loop

Say you want the total of the positive values in a list, ignoring anything that is zero or below. Here is the thinking, one step at a time.

  1. Start the total. Make it before the loop, because it has to exist before the first value is looked at, and start it at 0, because nothing has been added yet.
  2. Test each value. The total of the whole list can only be known once every value has been seen, so the loop never stops early. The if decides whether this value belongs in the total.
  3. Grow the total when the test says yes.
  4. Use the total after the loop. Inside the loop it is only a running total.
def positive_total(values):
    total = 0
    for value in values:
        if value > 0:
            total = total + value
    return total
public static int positiveTotal(int[] values) {
    int total = 0;
    for (int value : values) {
        if (value > 0) {
            total = total + value;
        }
    }
    return total;
}

A common mistake: setting total back to 0 inside the loop as well as before it. Then the total is reset every time round, and only the last value can ever be in it. If a total seems to forget earlier values, check where it is set to 0.

Searching: stop when you find it, or at the end

Now say you want to know whether a list has any negative value in it. You can answer "yes" the moment you see one. You can only answer "no" once you have looked at every value.

  1. Start at the first position, with an index at 0.
  2. Keep going while there are values left and you have not found one. Two conditions, and both matter: the first stops the index running off the end of the list.
  3. Move the index on by one each time round. Forget i = i + 1 and the loop can run forever.
  4. After the loop, the index tells you what happened. If it stopped before the end, it stopped on a negative value.
def has_negative(values):
    i = 0
    while i < len(values) and values[i] >= 0:
        i = i + 1
    return i < len(values)
public static boolean hasNegative(int[] values) {
    int i = 0;
    while (i < values.length
            && values[i] >= 0) {
        i = i + 1;
    }
    return i < values.length;
}

The order of the two conditions matters. When i has reached the end of the list, the first condition is false and the second is never checked, which is exactly what stops it reading past the end. Swap them and a list with no negative value reads past the end and stops with an error.

A common mistake: answering "no" as soon as one value is not negative. The first value being fine tells you nothing about the rest. A search can say "yes" early, but "no" only at the end.

The pattern to remember

Before the loop, set up the variable that will hold the answer. In the loop, look at one value and update that variable. After the loop, use it. Next, try it yourself on the questions below.

Exercise 5.8.15.8.1 · Write itCount above a limit

Write a function that returns how many values in a list (an array in Java) of whole numbers are greater than a limit.

  1. Only values strictly greater than limit count. A value equal to limit does not.
  2. An empty list returns 0.
  3. The values and the limit can be negative.

Only the number your function returns is checked.

def count_above(values: list[int], limit: int) -> int

Examples

Your function is tested on 9 cases: the 3 examples below, and 6 hidden ones that check the rules above.

  • count_above([3, 8, 5, 10], 5) should return 2: 8 and 10 count; 5 does not, because it equals the limit (rule 1)
  • count_above([], 4) should return 0: an empty list (rule 2)
  • count_above([9, 2, 7], 5) should return 2: 9 and 7 count, the first value as well as the last (rule 1)

public static int countAbove(int[] values, int limit)

Checking whether Java answers can run here.

Examples

Your function is tested on 9 cases: the 3 examples below, and 6 hidden ones that check the rules above.

  • countAbove(new int[]{3, 8, 5, 10}, 5) should return 2: 8 and 10 count; 5 does not, because it equals the limit (rule 1)
  • countAbove(new int[]{}, 4) should return 0: an empty list (rule 2)
  • countAbove(new int[]{9, 2, 7}, 5) should return 2: 9 and 7 count, the first value as well as the last (rule 1)
solution.pySolution.java

Exercise 5.8.25.8.2 · Write itThe average

Write a function that returns the average (the mean) of a list (an array in Java) of whole numbers.

  1. The list always has at least one value.
  2. The values are whole numbers from -1000000 to 1000000, and can be negative. The list has at most 1000 values.
  3. Return the average as a decimal number, and do not round it: the average of 2 and 3 is 2.5, not 2.

Only the number your function returns is checked.

def average(values: list[int]) -> float

Examples

Your function is tested on 9 cases: the 3 examples below, and 6 hidden ones that check the rules above.

  • average([2, 3]) should return 2.5: an average that is not a whole number (rule 3)
  • average([4]) should return 4.0: one value is its own average
  • average([-1, -2]) should return -1.5: negative values (rule 2)

public static double average(int[] values)

Checking whether Java answers can run here.

Examples

Your function is tested on 9 cases: the 3 examples below, and 6 hidden ones that check the rules above.

  • average(new int[]{2, 3}) should return 2.5: an average that is not a whole number (rule 3)
  • average(new int[]{4}) should return 4.0: one value is its own average
  • average(new int[]{-1, -2}) should return -1.5: negative values (rule 2)
solution.pySolution.java

Exercise 5.8.3 · Trace itTrace: running total

Complete the trace table for this Python code. Then answer the question below the table. [3]

Line 1: values = [3, 5, 2, 7, 4]
Line 2: total = 0
Line 3: i = 0
Line 4: while total <= 10:
Line 5, indented 1 level: total = total + values[i]
Line 6, indented 1 level: i = i + 1
Line 7: print(total)

Fill in one row each time a line changes total or i, or prints something. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Python shows them: 3 and 3.0 are different, and text goes in quotes. In the output column, write exactly what appears on screen, with no quotes around it.

Rowtotalioutput
1
2
3
4
5
6
7
8
9
10
11

Exercise 5.8.3 · Trace itTrace: running total (Java)

Complete the trace table for this Java code. Then answer the question below the table. [3]

Line 1: int[] values = {3, 5, 2, 7, 4};
Line 2: int total = 0;
Line 3: int i = 0;
Line 4: while (total <= 10) {
Line 5, indented 1 level: total = total + values[i];
Line 6, indented 1 level: i = i + 1;
Line 7: }
Line 8: System.out.println(total);

Fill in one row each time a line changes total or i, or prints something. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Java shows them: 3 and 3.0 are different, and text goes in quotes. In the output column, write exactly what appears on screen, with no quotes around it.

Rowtotalioutput
1
2
3
4
5
6
7
8
9
10
11