AP Computer Science A · Unit 2 lecture · Part 8 of 12 · 10 min

2.9 Implementing selection and iteration algorithmsThe patterns you'll write again and again

Mr. Thompkins
Here's a secret: almost every loop on the AP exam is one of about seven patterns. Learn their shapes once and you'll recognize them everywhere, in multiple choice and on the free response.

Each pattern has three parts: something set up before the loop, something done on every pass, and something used after the loop. The CED names these: sums and averages, counting items that meet a criterion, finding a minimum or maximum, checking whether any or all values meet a criterion, testing divisibility, and pulling apart the digits of an integer.

PatternBefore the loopInside the loopAfter the loop
Sum, averagesum = 0sum += value;(double) sum / count
Countcount = 0if (test) count++;use count
Maximummax = first valueif (value > max) max = value;use max
Minimummin = first valueif (value < min) min = value;use min
Is there any?if (test) return true;return false;
Are all?if (!test) return false;return true;
Digits of n > 0d = n % 10; n /= 10;loop while n > 0
The standard patterns. On an FRQ, you'll often combine two: a count inside a digit loop, or a max inside a String loop.

Maximum and minimum

To find the largest value, keep a variable max holding the biggest value seen so far, and replace it whenever you see something bigger. The trick is the starting value. Start max at the first real value, not at 0: if every value is negative, a max that started at 0 would wrongly report 0. If there's no first value handy, start at Integer.MIN_VALUE for a max, or Integer.MAX_VALUE for a min, so any real value replaces it.

?Wait, what's Integer.MIN_VALUE again?
It's the smallest value an int can hold, -2147483648 (Unit 1). Every other int is bigger, so a max that starts there gets replaced by the very first real value. Integer.MAX_VALUE, 2147483647, plays the same role for a min.
1public static int largestDigit(int n)2{3    int max = n % 10;14    n /= 10;15    while (n > 0)26    {7        int d = n % 10;8        if (d > max)39        {10            max = d;311        }12        n /= 10;13    }14    return max;415}
  1. line 3-4 Start max at a real value: the last digit
  2. line 5 One pass per remaining digit
  3. line 8-10 The max pattern: replace when bigger
  4. line 14 Return after the loop has seen every digit
The max pattern inside the digits pattern. largestDigit(4729) returns 9, and largestDigit(90210) returns 9. Run under Java 17.

Any and all, with an early return

To check whether any value meets a test, return true the moment you find one, and return false only after the loop has checked everything. To check whether all values meet a test, flip it: return false the moment one fails, and true after the loop. The classic mistake is putting return false in an else inside the loop. Then the method gives up after looking at just the first value.

1public static boolean isPrime(int n)2{3    if (n < 2)14    {5        return false;16    }7    for (int d = 2; d * d <= n; d++)28    {9        if (n % d == 0)310        {11            return false;312        }13    }414    return true;15}
  1. line 3-5 0, 1 and negatives are not prime
  2. line 7 Divisors pair up, so stop at the square root
  3. line 9-11 One divisor is enough: return false at once
  4. line 13 Only after every d failed: return true
An "is there any divisor?" search. isPrime(13) and isPrime(97) are true; isPrime(1), isPrime(9) and isPrime(49) are false. Run under Java 17.
?Wait, why does d * d <= n work as the stopping test?
Divisors come in pairs that multiply to n: for 36, 2 × 18, 3 × 12, 4 × 9, 6 × 6. In every pair, one of the two is at most the square root of n. So if no d with d * d <= n divides n, nothing bigger will either. Testing d <= n would also be correct, just slower.
Pause and think
A student writes the max pattern with int max = 0; before a loop over the values -4, -9 and -2. What does the method report, and what should it report?
I thought about it. Show me
It reports 0, but the correct answer is -2. None of the negative values is greater than 0, so max is never replaced. Starting max at the first value, -4, or at Integer.MIN_VALUE fixes it.
Write a counting method
Write a static method countDivisors(int n) that returns how many positive integers divide n evenly. Precondition: n >= 1. Then trace it for n = 12.
  1. Pattern: count. Before the loop, int count = 0;.
  2. Every candidate from 1 to n: for (int d = 1; d <= n; d++). A divisor leaves no remainder: if (n % d == 0) { count++; }
    Why?
    The <= matters: n always divides itself, so d must reach n.
  3. After the loop, return count;. It's outside the loop, so it runs only after every d has been checked.
  4. Trace for 12: the d values with 12 % d == 0 are 1, 2, 3, 4, 6 and 12. countDivisors(12) returns 6.

Answer:

public static int countDivisors(int n)
{
    int count = 0;
    for (int d = 1; d <= n; d++)
    {
        if (n % d == 0)
        {
            count++;
        }
    }
    return count;
}

countDivisors(12) returns 6 (checked under Java 17; countDivisors(13) returns 2).

Stuck? Get a hint
  1. Which pattern is this: sum, count, max, or any?
  2. Try every d from 1 up to and including n. How do you test "d divides n"?
  3. Where does return go, inside the loop or after it?
Check yourself
This method should return true if any digit of n is 7, where n > 0. What does hasSeven(172) return, and is the method correct?
public static boolean hasSeven(int n)
{
    while (n > 0)
    {
        if (n % 10 == 7)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    return false;
}
  1. AIt returns false; the method is wrong because it gives up after checking only the last digit.
  2. BIt returns true; the method is correct.
  3. CIt returns false; the method is correct.
  4. DIt returns true; the method is wrong for numbers that end in 7.
Show the answer

A. The last digit of 172 is 2, which isn't 7, so the else runs return false right away, on the first pass. The 7 in the middle is never checked. The fix: delete the else, and put return false after the loop. Choice C is the trap: 172 does contain a 7, so false is the wrong answer.

  • Every pattern: set up before the loop, update inside it, use the result after it.
  • Start a max or min at the first value (or Integer.MIN_VALUE / Integer.MAX_VALUE), never at 0.
  • Any: return true inside the loop, false after it. All: return false inside, true after.
  • Divisibility: n % d == 0. Digits: n % 10 and n /= 10 while n > 0.