Implementing Selection and Iteration Algorithms

You now have every building block you need to make a program decide (if statements) and repeat (while and for loops). This topic is about putting those blocks together to solve problems that come up again and again: What is the total of these prices? What is the average score? How many days were hot? What was the coldest night? Programmers solve these so often that each has a well-known shape. A standard algorithm is a step-by-step solution to a common problem that programmers reuse, adjusting the details each time. Once you recognize the shape, you can read, trace, and fix code that uses it quickly, and you can combine shapes to solve new problems.

The first and most common problem is adding up a series of numbers. Think about how you add a stack of receipts by hand. You do not look at all of them at once. You start at zero, look at one receipt, add its amount to what you have so far, then move to the next receipt and add again. The number in your head is a running total: the sum of every value you have looked at so far.

A program does the same thing with a variable. An accumulator is a variable that collects a result a little at a time as a loop runs; when the result is a sum, the accumulator holds the running total. Every sum algorithm has the same three parts:

The order matters. The total must be set to zero once, before the loop starts, so that the additions on later passes are not thrown away. The += from Topic 1.6 does the adding: total += value; means total = total + value;, so each pass builds on what the earlier passes stored.

int total = 0;
for (int number = 1; number <= 5; number++)
{
    total += number;
}
System.out.println(total);

15

Now change where the values come from. Without lists of data (those come in Unit 4), a program usually gets a series of values by reading them one at a time. This example reads them with a Scanner. The first number in the input says how many prices follow, so a for loop can run exactly that many times. A keyboard Scanner would work the same way; this guide builds the Scanner from a string so the output is always the same.

import java.util.Scanner;

public class ReceiptTotal
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("4 3.25 1.50 2.75 4.00");
        int itemCount = input.nextInt();
        double total = 0.0;
        for (int item = 1; item <= itemCount; item++)
        {
            double price = input.nextDouble();
            total += price;
        }
        System.out.print("Total: ");
        System.out.println(total);
    }
}

Total: 11.5

int total = 0;
for (int number = 1; number <= 5; number++)
{
    total = 0;
    total += number;
}
System.out.println(total);

int total = 0;
for (int k = 3; k <= 12; k += 3)
{
    total += k;
}
System.out.println(total);

int total = 0;
for (int number = 1; number < 10; number++)
{
    total += number;
}
System.out.println(total);

for (int number = 1; number <= 10; number++)

A teacher does not usually want the total of a class’s quiz scores; she wants the average. A weather report gives the average rainfall, not the sum. To find an average (also called the mean), you add up the values and divide by how many values there are. So an average algorithm is the sum algorithm from 2.9.1 plus one division after the loop.

The division is where things go wrong, because of a rule from Topic 1.3: when both numbers are int, / throws away the decimal part. A sum of whole-number scores and a count of scores are both int, so sum / count can lose information. The fix, from Topic 1.5, is to cast one of them to double before dividing, so the division is done with decimals.

import java.util.Scanner;

public class RainfallAverage
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("5 12 7 0 9 4");
        int days = input.nextInt();
        int totalRain = 0;
        for (int day = 1; day <= days; day++)
        {
            totalRain += input.nextInt();
        }
        double average = (double) totalRain / days;
        System.out.print("Average rainfall: ");
        System.out.println(average);
    }
}

Average rainfall: 6.4

Where the cast goes matters. This snippet tries three ways with the same total and count:

int totalRain = 32;
int days = 5;
System.out.println(totalRain / days);
System.out.println((double) (totalRain / days));
System.out.println((double) totalRain / days);

6
6.0
6.4

The middle one is the trap. It looks like it uses a cast, but by the time the cast happens, the integer division has already thrown away the .4. Casting 6 to a double gives 6.0, not 6.4.

So far the program knew how many values were coming. Often it does not: a teacher types scores until she is done. You met the usual way to handle this in Topic 2.7: a sentinel value, a special value that is not real data and that means “stop reading.” Quiz scores are never negative, so -1 works as a sentinel. Because the program does not know in advance how many values there will be, it uses a while loop (Topic 2.7) and a second accumulator. A counter is an accumulator that adds one each time something happens; here it adds one for each real value read.

import java.util.Scanner;

public class QuizAverage
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("88 92 75 90 -1");
        int sum = 0;
        int count = 0;
        int score = input.nextInt();
        while (score != -1)
        {
            sum += score;
            count++;
            score = input.nextInt();
        }
        if (count > 0)
        {
            double average = (double) sum / count;
            System.out.print("Average: ");
            System.out.println(average);
        }
        else
        {
            System.out.println("No scores");
        }
    }
}

Average: 86.25

import java.util.Scanner;

public class AverageNoGuard
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("-1");
        int sum = 0;
        int count = 0;
        int score = input.nextInt();
        while (score != -1)
        {
            sum += score;
            count++;
            score = input.nextInt();
        }
        int average = sum / count;
        System.out.println(average);
    }
}

Exception in thread "main" java.lang.ArithmeticException: / by zero
	at AverageNoGuard.main(AverageNoGuard.java:17)

import java.util.Scanner;

public class SentinelZeroScore
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("10 0 5 -1");
        int sum = 0;
        int count = 0;
        int score = input.nextInt();
        while (score != -1)
        {
            sum += score;
            count++;
            score = input.nextInt();
        }
        System.out.println((double) sum / count);
    }
}

In 2.9.2 you counted every value. Often you need to count only some of them. How many days this week were over 90 degrees? How many students scored in the B range? How many numbers from 1 to 100 are even? Each question asks for a frequency: the number of times a particular condition is true.

The plan is the counter from the average algorithm, which added one for every value, with an if statement wrapped around the count++. Start it at 0 before the loop. Inside the loop, test the current value; only when the condition is true, add one.

int count = 0;
// loop over the values:
    if (condition about the current value)
    {
        count++;
    }
// after the loop, count holds the answer

Why 0 and not 1? Before the loop has checked anything, no value has met the condition. Starting at 1 would claim one match before seeing any data.

import java.util.Scanner;

public class HotDays
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("7 88 93 91 79 95 90 84");
        int days = input.nextInt();
        int hotCount = 0;
        for (int day = 1; day <= days; day++)
        {
            int temp = input.nextInt();
            if (temp > 90)
            {
                hotCount++;
            }
        }
        System.out.print("Hot days: ");
        System.out.println(hotCount);
    }
}

Hot days: 3

The condition can be anything you learned in Topics 2.2 through 2.6, including compound conditions. Here the question is how many scores fall from 70 to 89, including both ends.

import java.util.Scanner;

public class ScoreBand
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("6 72 95 89 64 70 90");
        int students = input.nextInt();
        int inBand = 0;
        for (int student = 1; student <= students; student++)
        {
            int score = input.nextInt();
            if (score >= 70 && score <= 89)
            {
                inBand++;
            }
        }
        System.out.print("Scores from 70 to 89: ");
        System.out.println(inBand);
    }
}

Scores from 70 to 89: 3

import java.util.Scanner;

public class HotDaysNoBraces
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("7 88 93 91 79 95 90 84");
        int days = input.nextInt();
        int hotCount = 0;
        for (int day = 1; day <= days; day++)
        {
            int temp = input.nextInt();
            if (temp > 90)
                System.out.println(temp);
                hotCount++;
        }
        System.out.print("Hot days: ");
        System.out.println(hotCount);
    }
}

93
91
95
Hot days: 7

if (temp > 90)
{
    System.out.println(temp);
    hotCount++;
}

import java.util.Scanner;

public class FreezeCount
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("5 32 15 40 32 28");
        int nights = input.nextInt();
        int freezing = 0;
        int aboveFreezing = 0;
        for (int night = 1; night <= nights; night++)
        {
            int temp = input.nextInt();
            if (temp <= 32)
            {
                freezing++;
            }
            else
            {
                aboveFreezing++;
            }
        }
        System.out.println(freezing);
        System.out.println(aboveFreezing);
    }
}

Can 84 marbles be shared equally among 7 friends with none left over? Is this year a multiple of 4? Is a number even? All of these ask whether one integer is evenly divisible by another: dividing leaves a remainder of zero.

You already have the tool. From Topic 1.3, a % b gives the remainder when a is divided by b. If the remainder is 0, then b goes into a exactly. So the test “is a evenly divisible by b?” is the Boolean expression

a % b == 0

and “is a not evenly divisible by b?” is a % b != 0. In this course, the number being divided is never negative and the number you divide by is always positive, so these are the only cases you need.

int marbles = 84;
int friends = 7;
System.out.println(marbles % friends);
if (marbles % friends == 0)
{
    System.out.println("7 friends: shares evenly");
}
friends = 5;
System.out.println(marbles % friends);
if (marbles % friends == 0)
{
    System.out.println("5 friends: shares evenly");
}
else
{
    System.out.println("5 friends: some left over");
}

0
7 friends: shares evenly
4
5 friends: some left over

The most common divisibility test is checking whether a number is even, which means “divisible by 2.” Every whole number leaves a remainder of either 0 or 1 when divided by 2:

for (int n = 6; n <= 9; n++)
{
    System.out.print(n);
    System.out.print(" % 2 is ");
    System.out.println(n % 2);
}

6 % 2 is 0
7 % 2 is 1
8 % 2 is 0
9 % 2 is 1

So n % 2 == 0 means n is even, and n % 2 != 0 means n is odd.

A divisibility test becomes much more powerful inside a loop. Combine it with the counting pattern from 2.9.3, and you can find every number that divides another.

int number = 12;
int divisorCount = 0;
for (int d = 1; d <= number; d++)
{
    if (number % d == 0)
    {
        System.out.print(d);
        System.out.print(" ");
        divisorCount++;
    }
}
System.out.println();
System.out.print("Divisors: ");
System.out.println(divisorCount);

1 2 3 4 6 12
Divisors: 6

int marbles = 84;
int friends = 7;
System.out.println(friends % marbles);
if (friends % marbles == 0)
{
    System.out.println("Shares evenly");
}
else
{
    System.out.println("Some left over");
}

7
Some left over

int evenCount = 0;
for (int n = 1; n <= 10; n++)
{
    if (n / 2 == 0)
    {
        evenCount++;
    }
}
System.out.println(evenCount);

if (n % 2 == 0)

for (int n = 1; n <= 30; n++)
{
    if (n % 4 == 0 && n % 6 == 0)
    {
        System.out.println(n);
    }
}

A credit card number has a check digit that catches typos. A puzzle asks for the sum of the digits of a number. A program reports how many digits a number has. Each needs the individual digits of an int, but an int is a single number, not a row of separate digits. How do you get at them?

The answer uses the two kinds of integer division from Topic 1.3, with 10:

• number % 10 is the last digit (the ones digit). Dividing by 10 leaves the ones digit as the remainder: 4072 % 10 is 2.
• number / 10 drops the last digit. Integer division by 10 throws away the ones digit: 4072 / 10 is 407.

Why 10? Our numbers are written in base ten: each place is worth ten times the place to its right. Dividing by 10 shifts every digit one place to the right, and whatever falls off the end is the remainder. You can combine the two to reach any digit:

int number = 4072;
System.out.println(number % 10);
System.out.println(number / 10);
System.out.println(number / 10 % 10);
System.out.println(number / 100 % 10);

Line 4 has no parentheses but still works left to right: / and % have the same precedence, so number / 10 happens first and % 10 is applied to its result.

To visit every digit without knowing how many there are, put the two steps in a while loop: take the last digit, then drop it, and repeat until nothing is left. When the number reaches 0, every digit has been removed.

int number = 4072;
while (number > 0)
{
    int digit = number % 10;
    System.out.println(digit);
    number = number / 10;
}

2
7
0
4

Because the loop destroys the number as it goes, a program that still needs the original value copies it first. This next example does that and uses two accumulators at once: a sum of the digits and a count of the digits.

int number = 9035;
int remaining = number;
int digitSum = 0;
int digitCount = 0;
while (remaining > 0)
{
    digitSum += remaining % 10;
    digitCount++;
    remaining /= 10;
}
System.out.print(number);
System.out.print(" has ");
System.out.print(digitCount);
System.out.print(" digits that add up to ");
System.out.println(digitSum);

9035 has 4 digits that add up to 17

These digit algorithms assume the number is not negative. That is the usual situation (counts, years, ID numbers), and the remainder operator with negative numbers is outside this course.

int number = 0;
int digitCount = 0;
while (number > 0)
{
    digitCount++;
    number /= 10;
}
System.out.println(digitCount);

int number = 0;
int digitCount = 0;
if (number == 0)
{
    digitCount = 1;
}
while (number > 0)
{
    digitCount++;
    number /= 10;
}
System.out.println(digitCount);

int n = 615;
while (n > 0)
{
    System.out.print(n % 10);
    n /= 10;
}
System.out.println();

Which player had the highest score? What was the coldest night of the week? These ask for the maximum (largest value) or the minimum (smallest value) in a series.

Think about how you would find the tallest person in a line if you could see only one person at a time. You would remember the tallest person so far. You look at the first person: so far, they are the tallest. For each next person, you compare: if this one is taller than the one you remember, you remember this one instead. When you reach the end, the person you remember is the tallest of all.

A program does exactly that with a variable that holds the best so far. Two decisions make up the algorithm:

1. Where to start. Before the loop, the best-so-far variable needs a starting value. The safest choice is the first value itself, since it is a real piece of data. Another choice is a value that every real value is guaranteed to beat: Integer.MAX_VALUE when looking for a minimum (every int is at most that), or Integer.MIN_VALUE when looking for a maximum.
2. How to update. Inside the loop, compare the current value with the best so far. For a maximum, if (value > best); for a minimum, if (value < best). Only when the comparison is true, replace the best so far.

import java.util.Scanner;

public class HighestScore
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("5 71 88 64 93 80");
        int players = input.nextInt();
        int highest = input.nextInt();
        for (int player = 2; player <= players; player++)
        {
            int score = input.nextInt();
            if (score > highest)
            {
                highest = score;
            }
        }
        System.out.print("Highest: ");
        System.out.println(highest);
    }
}

Highest: 93

Now vary three things: look for the minimum, start at Integer.MAX_VALUE instead of the first value, and also remember where the minimum happened. Recording the position is a small addition: whenever the best so far changes, store the day too.

import java.util.Scanner;

public class ColdestDay
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("5 -3 4 -8 2 -5");
        int days = input.nextInt();
        int coldest = Integer.MAX_VALUE;
        int coldestDay = 0;
        for (int day = 1; day <= days; day++)
        {
            int temp = input.nextInt();
            if (temp < coldest)
            {
                coldest = temp;
                coldestDay = day;
            }
        }
        System.out.print("Coldest: ");
        System.out.print(coldest);
        System.out.print(" on day ");
        System.out.println(coldestDay);
    }
}

Coldest: -8 on day 3

import java.util.Scanner;

public class MaxStartZero
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("4 -6 -2 -9 -4");
        int days = input.nextInt();
        int warmest = 0;
        for (int day = 1; day <= days; day++)
        {
            int temp = input.nextInt();
            if (temp > warmest)
            {
                warmest = temp;
            }
        }
        System.out.println(warmest);
    }
}

import java.util.Scanner;

public class MaxStartFirst
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("4 -6 -2 -9 -4");
        int days = input.nextInt();
        int warmest = input.nextInt();
        for (int day = 2; day <= days; day++)
        {
            int temp = input.nextInt();
            if (temp > warmest)
            {
                warmest = temp;
            }
        }
        System.out.println(warmest);
    }
}

import java.util.Scanner;

public class MinUpdates
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("4 12 9 15 9");
        int count = input.nextInt();
        int lowest = input.nextInt();
        int updates = 0;
        for (int i = 2; i <= count; i++)
        {
            int value = input.nextInt();
            if (value < lowest)
            {
                lowest = value;
                updates++;
            }
        }
        System.out.print("Lowest: ");
        System.out.println(lowest);
        System.out.print("Updates: ");
        System.out.println(updates);
    }
}

Lowest: 9
Updates: 1

Real programs rarely use just one of these algorithms. They run several in the same loop, each with its own variable. This program reads a week of step counts from a fitness tracker and reports the total, the average, how many days met a 10,000-step goal, and the best day. Comments (Topic 1.8) label the job of each variable.

import java.util.Scanner;

public class StepReport
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("7 8200 10450 6100 12000 9800 10450 6000");
        int days = input.nextInt();

        int total = 0;          // sum of all step counts
        int goalDays = 0;       // days with at least 10000 steps
        int best = 0;           // most steps in one day so far
        int bestDay = 0;        // the day that happened

        for (int day = 1; day <= days; day++)
        {
            int steps = input.nextInt();
            total += steps;
            if (steps >= 10000)
            {
                goalDays++;
            }
            if (day == 1 || steps > best)
            {
                best = steps;
                bestDay = day;
            }
        }

        System.out.print("Total: ");
        System.out.println(total);
        System.out.print("Average: ");
        System.out.println((double) total / days);
        System.out.print("Goal days: ");
        System.out.println(goalDays);
        System.out.print("Best: ");
        System.out.print(best);
        System.out.print(" on day ");
        System.out.println(bestDay);
    }
}

Total: 63000
Average: 9000.0
Goal days: 3
Best: 12000 on day 4

The algorithms also combine in less obvious ways. There is an old shortcut for checking whether a number is divisible by 9: add up its digits, and if that sum is divisible by 9, so is the number. This snippet uses the digit algorithm to build a sum, then two divisibility tests to compare the shortcut with the direct check.

int number = 7848;
int remaining = number;
int digitSum = 0;
while (remaining > 0)
{
    digitSum += remaining % 10;
    remaining /= 10;
}
System.out.print("Digit sum: ");
System.out.println(digitSum);
if (digitSum % 9 == 0)
{
    System.out.println("Digit sum is a multiple of 9");
}
if (number % 9 == 0)
{
    System.out.println("Number is a multiple of 9");
}

Digit sum: 27
Digit sum is a multiple of 9
Number is a multiple of 9

• A sum uses an accumulator that starts at 0 before the loop, gains one value per pass with +=, and is used after the loop. Resetting it inside the loop throws away the running total.
• An average is the sum divided by the count. Write (double) sum / count so the division keeps its decimal part, and check that the count is greater than zero first. A sentinel value lets a while loop read an unknown number of values.
• Counting how often a condition is met puts count++ inside an if inside the loop. The condition, including its boundary (> versus >=), decides what is counted.
• a % b == 0 tests whether a is evenly divisible by b; n % 2 == 0 tests for an even number. Inside a loop, it can find every divisor of a number.
• % 10 gives the last digit of a nonnegative integer and / 10 removes it; a while (number > 0) loop repeating both visits every digit from right to left.
• A minimum or maximum keeps a best-so-far variable that starts at the first value (or a value every real value will beat) and is replaced whenever the current value is smaller or larger.

int sum = 0;
int count = 0;
for (int k = 1; k <= 10; k++)
{
    if (k % 3 == 0)
    {
        sum += k;
    }
    else
    {
        count++;
    }
}
System.out.println(sum);
System.out.println(count);

int count = 0;
for (int n = 1; n <= 50; n++)
{
    if (n % 2 == 0 || n % 3 == 0)
    {
        count++;
    }
}
System.out.println(count);

if (n % 2 == 0 && n % 3 == 0)

int number = 70300;
int zeros = 0;
while (number > 0)
{
    if (number % 10 == 0)
    {
        zeros++;
    }
    number /= 10;
}
System.out.print("Zeros: ");
System.out.println(zeros);

import java.util.Scanner;

public class TieLastDay
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner("5 40 55 30 55 20");
        int days = input.nextInt();
        int best = input.nextInt();
        int bestDay = 1;
        for (int day = 2; day <= days; day++)
        {
            int sales = input.nextInt();
            if (sales >= best)
            {
                best = sales;
                bestDay = day;
            }
        }
        System.out.print("Best day: ");
        System.out.println(bestDay);
    }
}

int number = 2468;
int sum = 0;
int largest = 0;
while (number > 0)
{
    int digit = number % 10;
    sum += digit;
    if (digit > largest)
    {
        largest = digit;
    }
    number /= 10;
}
System.out.println(sum);
System.out.println(largest);
System.out.println(sum % largest == 0);

20
8
false

• I can trace a sum with an accumulator and explain why it starts at 0 before the loop. Reread
• I can compute an average without losing the decimal part, and explain what a sentinel value is for. Reread
• I can trace a loop that counts how many values meet a condition, including at the boundary. Reread
• I can use % to test whether one integer is evenly divisible by another. Reread
• I can use % 10 and / 10 in a loop to visit every digit of an integer. Reread
• I can find a minimum or maximum and explain how the starting value can change the answer. Reread
• I can trace a program that runs several of these algorithms in the same loop. Reread