2.9 Implementing Selection and Iteration Algorithms

1. Evenly divisible: use the remainder

There are standard algorithms to identify if an integer is or is not evenly divisible by another integer 2.9.A.1. The test is the remainder operator: a % b == 0 means a is evenly divisible by b.

int year = 2028;
if (year % 4 == 0) {
    System.out.println(year + " is divisible by 4");
}
for (int n = 1; n <= 15; n++) {
    if (n % 3 == 0 && n % 5 == 0) {
        System.out.print("both ");
    } else if (n % 3 == 0) {
        System.out.print("three ");
    } else if (n % 5 == 0) {
        System.out.print("five ");
    }
}
System.out.println();

Output:

2028 is divisible by 4
three five three three five three both 

The test for “divisible by both” comes first. If n % 3 == 0 came first, 15 would print “three” and never reach “both”.

Watch out: to test for odd numbers, write n % 2 != 0. In Java, -7 % 2 is -1, so n % 2 == 1 is false for negative odd numbers.

System.out.println(-7 % 2);
System.out.println(-7 % 2 != 0);

Output:

-1
true

2. The individual digits of an integer

There are standard algorithms to identify the individual digits in an integer 2.9.A.1. n % 10 is the last digit, and n / 10 (integer division) removes the last digit. Repeat while n > 0.

int n = 4072;
int digitSum = 0;
int digitCount = 0;
while (n > 0) {
    int digit = n % 10;
    System.out.println("digit: " + digit);
    digitSum += digit;
    digitCount++;
    n = n / 10;
}
System.out.println("sum " + digitSum + ", count " + digitCount);

Output:

digit: 2
digit: 7
digit: 0
digit: 4
sum 13, count 4

n at the check	n > 0	digit = n % 10	digitSum	n / 10
4072	true	2	2	407
407	true	7	9	40
40	true	0	9	4
4	true	4	13	0
0	false

Notes:

• The digits come out from right to left (ones digit first).
• The loop destroys n. Copy it first if you need the original value later.
• If n starts at 0, the loop runs zero times and digitCount stays 0. If the number 0 should count as one digit, handle it with an if before the loop.

The same pattern can build a number with the digits reversed:

int n = 1234;
int reversed = 0;
while (n > 0) {
    reversed = reversed * 10 + n % 10;
    n /= 10;
}
System.out.println(reversed);

Output:

4321

3. Frequency: how often a criterion is met

There are standard algorithms to determine the frequency with which a specific criterion is met 2.9.A.1. Pattern: set a counter to 0 before the loop, test each value with an if, add 1 when the test passes, use the counter after the loop.

How many numbers from 1 to 50 are divisible by 6 or by 8?

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

Output:

12

There are 8 multiples of 6 and 6 multiples of 8 up to 50, but 24 and 48 are both, and || counts them only once: 8 + 6 - 2 = 12.

Watch out: writing int count = 0; inside the loop resets the counter every iteration, and the code would not compile here anyway, because count would not exist after the loop.

4. Minimum and maximum

There are standard algorithms to determine a minimum or maximum value 2.9.A.1. Pattern: keep the best value so far, and replace it whenever a new value beats it.

A shop sells a game at a price from 1 to 10 dollars. At price p, it expects to earn p * (100 - 8 * p) dollars. Which price earns the most?

int bestPrice = 1;
int bestIncome = 1 * (100 - 8 * 1);
for (int p = 2; p <= 10; p++) {
    int income = p * (100 - 8 * p);
    if (income > bestIncome) {
        bestIncome = income;
        bestPrice = p;
    }
}
System.out.println("Best price: " + bestPrice + ", income: " + bestIncome);

Output:

Best price: 6, income: 312

The minimum and maximum of the digits of a number use the same idea. Here the starting values come from the Java Quick Reference: Integer.MAX_VALUE is larger than any digit, and Integer.MIN_VALUE is smaller than any digit, so the first digit always replaces them.

int n = 58291;
int smallest = Integer.MAX_VALUE;
int largest = Integer.MIN_VALUE;
while (n > 0) {
    int d = n % 10;
    if (d < smallest) {
        smallest = d;
    }
    if (d > largest) {
        largest = d;
    }
    n /= 10;
}
System.out.println("min " + smallest + ", max " + largest);

Output:

min 1, max 9

Watch out: starting smallest at 0 would give a minimum of 0 for 58291, a digit it does not contain. Use two separate if statements (not if-else) when one value can update both the minimum and the maximum, as the first digit does here.

5. Sum and average

There are standard algorithms to compute a sum or average 2.9.A.1. Pattern: set the sum to 0 before the loop, add each value inside the loop, divide by the count after the loop. Cast to double to avoid integer division.

Average of the multiples of 7 between 1 and 40:

int sum = 0;
int count = 0;
for (int n = 1; n <= 40; n++) {
    if (n % 7 == 0) {
        sum += n;
        count++;
    }
}
System.out.println("sum " + sum + ", count " + count);
if (count != 0) {
    System.out.println(sum / count);
    double average = (double) sum / count;
    System.out.println(average);
}

Output:

sum 105, count 5
21
21.0

The multiples are 7, 14, 21, 28 and 35. Here the integer and the double averages agree, but try the digits of 4825: the sum is 19 and the count is 4, so 19 / 4 is 4 while (double) 19 / 4 is 4.75.

int sum = 19;
int count = 4;
System.out.println(sum / count);
System.out.println((double) sum / count);
System.out.println((double) (sum / count));

Output:

4
4.75
4.0

Watch out: (double) (sum / count) casts too late: the integer division has already thrown away the 0.75.