2.9 - Implementing Selection and Iteration Algorithms

There are some standard algorithm patterns you’ll see over and over in this course:

Checking if an integer is evenly divisible by another integer (using %)

Pulling out the individual digits of an integer

Counting how many times something meets a certain criteria

Finding a minimum or maximum value

Computing a sum or an average

Checking Divisibility

An integer a is evenly divisible by b when the remainder is 0, so check a % b == 0. The most common use is checking even or odd: a number is even when num % 2 == 0 and odd when num % 2 != 0.


int num = 84;
if (num % 7 == 0) {
    System.out.println(num + " is divisible by 7"); // prints, since 84 % 7 is 0
}
if (num % 2 != 0) {
    System.out.println(num + " is odd"); // doesn't print, since 84 % 2 is 0
}

Pulling Out Digits

num % 10 gives you the rightmost digit, and num / 10 chops that digit off (integer division). Repeat until the number hits 0 to visit every digit, from right to left.


int num = 4529;
while (num > 0) {
    int digit = num % 10; // rightmost digit
    System.out.println(digit);
    num = num / 10;       // drop the rightmost digit
}
// prints 9, 2, 5, 4 (one per line)

This loop changes num, so save a copy first if you still need the original. Also, if num starts at 0, the loop body never runs.

Counting (Frequency)

To count how often something happens, start a counter at 0 before the loop, then add 1 inside an if whenever the condition is true.


// how many numbers from 1 to 100 are divisible by 3 or by 5?
int count = 0;
for (int i = 1; i <= 100; i++) {
    if (i % 3 == 0 || i % 5 == 0) {
        count++;
    }
}
System.out.println(count); // 47

Finding a Minimum or Maximum

Keep a variable that holds the best value so far. Each time you get a new value, compare it and replace the best one if the new one is smaller (for a minimum) or larger (for a maximum).

The starting value matters. Start with the first value, or start a minimum at Integer.MAX_VALUE (a maximum at Integer.MIN_VALUE), so any real value replaces it. Starting a minimum at 0 is a classic bug: if every value is positive, 0 never gets replaced.


// largest digit in a number
int num = 38271;
int largest = num % 10; // start with the first digit we look at
while (num > 0) {
    int digit = num % 10;
    if (digit > largest) {
        largest = digit;
    }
    num = num / 10;
}
System.out.println(largest); // 8


// smallest value of x * x - 6 * x + 10 for x from 0 to 10, and where it happens
int min = Integer.MAX_VALUE;
int bestX = 0;
for (int x = 0; x <= 10; x++) {
    int y = x * x - 6 * x + 10;
    if (y < min) {
        min = y;
        bestX = x;
    }
}
System.out.println(min + " at x = " + bestX); // 1 at x = 3

Computing a Sum or Average

Start a sum at 0 before the loop and add each value to it inside the loop. For an average, divide the sum by how many values there were, and cast to double first so you don’t get integer division.


int sum = 0;
int count = 0;
for (int i = 1; i <= 10; i++) {
    sum += i;
    count++;
}
double average = (double) sum / count;
System.out.println(sum);     // 55
System.out.println(average); // 5.5
// without the cast, sum / count would be 5 (integer division)

If the count could be 0, check for that before dividing, since dividing an int by 0 throws an ArithmeticException.

Combining Patterns

Original algorithms usually mix these patterns. For example, a number is prime when it has exactly two divisors (1 and itself), so you can combine divisibility with counting:


int n = 29;
int divisors = 0;
for (int d = 1; d <= n; d++) {
    if (n % d == 0) {
        divisors++;
    }
}
boolean isPrime = (divisors == 2);
System.out.println(isPrime); // true

Back Next