2.9 Implementing selection and iteration algorithmsThe patterns you'll write again and again
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.
| Pattern | Before the loop | Inside the loop | After the loop |
|---|---|---|---|
| Sum, average | sum = 0 | sum += value; | (double) sum / count |
| Count | count = 0 | if (test) count++; | use count |
| Maximum | max = first value | if (value > max) max = value; | use max |
| Minimum | min = first value | if (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 > 0 | d = n % 10; n /= 10; | loop while n > 0 |
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?
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}
- line 3-4 Start max at a real value: the last digit
- line 5 One pass per remaining digit
- line 8-10 The max pattern: replace when bigger
- line 14 Return after the loop has seen every digit
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}
- line 3-5 0, 1 and negatives are not prime
- line 7 Divisors pair up, so stop at the square root
- line 9-11 One divisor is enough: return false at once
- line 13 Only after every d failed: return true
?Wait, why does d * d <= n work as the stopping test?
I thought about it. Show me
- Pattern: count. Before the loop, int count = 0;.
- 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. - After the loop, return count;. It's outside the loop, so it runs only after every d has been checked.
- 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
- Which pattern is this: sum, count, max, or any?
- Try every d from 1 up to and including n. How do you test "d divides n"?
- Where does return go, inside the loop or after it?
public static boolean hasSeven(int n)
{
while (n > 0)
{
if (n % 10 == 7)
{
return true;
}
else
{
return false;
}
}
return false;
}- AIt returns false; the method is wrong because it gives up after checking only the last digit.
- BIt returns true; the method is correct.
- CIt returns false; the method is correct.
- 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.