2.9 Implementing Selection and Iteration Algorithms

Standard algorithms are like cooking recipes that every programmer should know. Just as every chef knows how to make a basic sauce, every programmer needs to know how to find a maximum value, check divisibility, or calculate an average. These algorithms combine the selection and iteration concepts you've learned into practical, reusable solutions.

The beauty of these standard algorithms is that they solve problems you'll encounter constantly. Need to check if a number is even? There's a pattern for that. Want to find the largest value in a dataset? Standard algorithm. These aren't just academic exercises - they're the building blocks of real programs.

What's really powerful is how these simple algorithms can be modified and combined. Once you understand how to find a maximum value, finding a minimum is nearly identical. Master extracting digits from a number, and you can solve problems involving digit manipulation. These patterns are your algorithmic toolkit.

• Major concepts: Divisibility checking, digit extraction, frequency counting, finding min/max, computing sums and averages
• Why this matters for AP: These exact algorithms appear in FRQs, especially FRQ1 and FRQ3, fundamental patterns tested in MCQs
• Common pitfalls: Off-by-one errors in loops, forgetting edge cases, integer division issues
• Key vocabulary: Modulo operator, integer division, accumulator, frequency counter, boundary values
• Prereqs: Understanding loops and conditionals, integer arithmetic, basic algorithm concepts

Key Concepts

more resources to help you study

practice questionscheatsheetscore calculator

Checking Divisibility - The Modulo Magic

The modulo operator (%) is your key to divisibility. When a % b equals 0, it means a is evenly divisible by b. This simple check powers many algorithms. Testing if a number is even? Check if n % 2 == 0. Testing if it's divisible by 10? Check if n % 10 == 0.

This pattern extends beyond basic checks. You can use modulo to check if a year is a leap year (divisible by 4, with special rules for centuries), if a number is prime (not divisible by anything except 1 and itself), or to implement cycling behavior (like days of the week).

Remember that modulo gives you the remainder after division. So 17 % 5 equals 2 because 17 divided by 5 is 3 with remainder 2. This remainder tells you about the divisibility relationship between the numbers.

Extracting Individual Digits

To work with individual digits of a number, combine modulo and integer division. The last digit of any number is n % 10. To get the next digit, divide by 10 (using integer division) and repeat. This pattern lets you process digits from right to left.

For example, with 1234: First digit is 1234 % 10 = 4. Then 1234 / 10 = 123. Next digit is 123 % 10 = 3. Continue until the number becomes 0. This algorithm is essential for problems involving digit sums, reversing numbers, or checking properties of digits.

The key insight is that our decimal system is base 10, so dividing by 10 shifts digits right, and modulo 10 extracts the rightmost digit. This same principle works in other bases too - just change the 10 to whatever base you're using.

Counting Frequencies

Frequency counting uses a counter variable that increments each time your criterion is met. Start with count = 0, check each item, and add 1 to count when the condition is true. This pattern is everywhere - counting passing grades, tallying votes, or finding how many times a character appears.

The structure is always similar: initialize a counter, loop through your data, use an if statement to check your criterion, increment the counter when true. After the loop, your counter holds the frequency. This combines iteration (the loop) with selection (the if statement).

Advanced frequency counting might track multiple criteria simultaneously (how many A's, B's, C's, etc.) or calculate percentages. But the core pattern remains: examine each item and count the ones that match your criteria.

Finding Minimum and Maximum

Finding the extreme values in a dataset follows a standard pattern. Initialize a variable to track the current min/max (often using the first value), then compare each subsequent value, updating when you find a new extreme. This algorithm efficiently finds the boundary values in one pass through the data.

For maximum: if the current value is greater than the tracked maximum, update the maximum. For minimum: if the current value is less than the tracked minimum, update the minimum. The comparisons are the only difference between finding min and max.

A crucial detail is initialization. You can start with the first value, or use extreme values (Integer.MAX_VALUE for finding minimum, Integer.MIN_VALUE for finding maximum). This ensures the first real value will properly update your tracker.

Computing Sums and Averages

Accumulation algorithms use a variable to build up a result. For sums, initialize to 0 and add each value. For products, initialize to 1 and multiply. This pattern of maintaining a running total is fundamental to many calculations.

Calculating averages adds one step: divide the sum by the count. Be careful with integer division - if both sum and count are integers, you might need to cast to double for accurate decimal results. Also watch for empty datasets where count is 0 to avoid division by zero.

The accumulator pattern extends beyond simple arithmetic. You can accumulate strings (concatenation), track running statistics, or build complex results. The key is maintaining state across iterations of a loop.

Code Examples

Let's implement these standard algorithms:

// Example: Divisibility checking algorithms
public class DivisibilityAlgorithms {
    // Check if a number is even
    public static boolean isEven(int n) {
        return n % 2 == 0;
    }

    // Check if a is divisible by b
    public static boolean isDivisible(int a, int b) {
        if (b == 0) return false;  // Avoid division by zero
        return a % b == 0;
    }

    // Count how many numbers in range are divisible by factor
    public static int countDivisible(int start, int end, int factor) {
        int count = 0;
        for (int i = start; i <= end; i++) {
            if (i % factor == 0) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println("Is 17 even? " + isEven(17));  // false
        System.out.println("Is 18 divisible by 3? " + isDivisible(18, 3));  // true
        System.out.println("Numbers from 1-20 divisible by 3: " + 
                          countDivisible(1, 20, 3));  // 6
    }
}

Digit extraction algorithms:

// Example: Working with individual digits
public class DigitAlgorithms {
    // Extract and print each digit (right to left)
    public static void printDigits(int n) {
        if (n == 0) {
            System.out.println(0);
            return;
        }

        while (n > 0) {
            int digit = n % 10;
            System.out.println("Digit: " + digit);
            n = n / 10;  // Remove last digit
        }
    }

    // Sum all digits in a number
    public static int sumDigits(int n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;  // Add last digit
            n /= 10;        // Remove last digit
        }
        return sum;
    }

    // Count how many times a digit appears
    public static int countDigit(int number, int target) {
        int count = 0;
        if (number == 0 && target == 0) return 1;

        while (number > 0) {
            if (number % 10 == target) {
                count++;
            }
            number /= 10;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println("Digits of 1234:");
        printDigits(1234);  // Prints 4, 3, 2, 1

        System.out.println("Sum of digits in 1234: " + sumDigits(1234));  // 10
        System.out.println("Count of 2's in 1222324: " + countDigit(1222324, 2));  // 4
    }
}

Min/max and accumulation algorithms:

// Example: Finding extremes and computing totals
public class AccumulationAlgorithms {
    // Find maximum value (assuming at least one value)
    public static int findMax(int[] values) {
        int max = values[0];  // Start with first value

        for (int i = 1; i < values.length; i++) {
            if (values[i] > max) {
                max = values[i];
            }
        }
        return max;
    }

    // Find minimum value with different initialization approach
    public static int findMin(int[] values) {
        int min = Integer.MAX_VALUE;  // Start with largest possible int

        for (int value : values) {
            if (value < min) {
                min = value;
            }
        }
        return min;
    }

    // Compute sum and average
    public static double computeAverage(int[] values) {
        if (values.length == 0) return 0;  // Handle empty array

        int sum = 0;
        for (int value : values) {
            sum += value;
        }

        // Cast to double for accurate division
        return (double) sum / values.length;
    }

    // Count values meeting criterion
    public static int countAboveThreshold(int[] values, int threshold) {
        int count = 0;
        for (int value : values) {
            if (value > threshold) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] scores = {85, 92, 78, 95, 88, 73, 91};

        System.out.println("Maximum: " + findMax(scores));  // 95
        System.out.println("Minimum: " + findMin(scores));  // 73
        System.out.println("Average: " + computeAverage(scores));  // 86.0
        System.out.println("Scores above 85: " + countAboveThreshold(scores, 85));  // 4
    }
}

Common Errors and Debugging

Integer Division in Averages

A classic mistake when computing averages with integers:

// WRONG: Integer division loses precision
int sum = 85 + 92 + 78;  // 255
int count = 3;
int average = sum / count;  // 85 (should be 85.0)

// CORRECT: Cast to double
double average = (double) sum / count;  // 85.0

// Also correct: Make one operand double
double average = sum / 3.0;  // 85.0

Always consider whether you need decimal precision in your results.

Forgetting Edge Cases

Standard algorithms often fail on edge cases:

// PROBLEM: What if array is empty?
public static int findMax(int[] values) {
    int max = values[0];  // ArrayIndexOutOfBoundsException if empty!
    // ... rest of method
}

// BETTER: Check for edge cases
public static int findMax(int[] values) {
    if (values.length == 0) {
        throw new IllegalArgumentException("Array cannot be empty");
    }
    int max = values[0];
    // ... rest of method
}

// PROBLEM: What about negative numbers?
int digitSum = 0;
int n = -123;  // Negative number
while (n > 0) {  // This will never execute!
    digitSum += n % 10;
    n /= 10;
}

Off-By-One Errors in Loops

Boundary conditions are tricky:

// PROBLEM: Should it be < or <=?
// Count integers from 1 to 10 divisible by 3
int count = 0;
for (int i = 1; i < 10; i++) {  // Misses 10!
    if (i % 3 == 0) count++;
}
// Returns 3 (counts 3, 6, 9) but misses 10

// CORRECT: Include the endpoint
for (int i = 1; i <= 10; i++) {
    if (i % 3 == 0) count++;
}
// Returns 3 (counts 3, 6, 9 - 10 isn't divisible by 3)

Practice Problems

Problem 1: Write a method that returns true if a number contains the digit 7.

Solution:

public static boolean containsSeven(int n) {
    if (n < 0) n = -n;  // Handle negative numbers

    while (n > 0) {
        if (n % 10 == 7) {
            return true;
        }
        n /= 10;
    }
    return false;
}

Problem 2: Find both the maximum value and its frequency in an array.

Solution:

public static void findMaxAndFrequency(int[] values) {
    if (values.length == 0) return;

    int max = values[0];
    int frequency = 1;

    // First pass: find maximum
    for (int i = 1; i < values.length; i++) {
        if (values[i] > max) {
            max = values[i];
            frequency = 1;  // Reset count for new max
        } else if (values[i] == max) {
            frequency++;    // Count occurrences of max
        }
    }

    System.out.println("Max: " + max + ", Frequency: " + frequency);
}

Problem 3: Calculate the percentage of passing scores (>= 70) in an array.

Solution:

public static double passingPercentage(int[] scores) {
    if (scores.length == 0) return 0.0;

    int passingCount = 0;
    for (int score : scores) {
        if (score >= 70) {
            passingCount++;
        }
    }

    return 100.0 * passingCount / scores.length;
}

AP Exam Connections

These standard algorithms appear constantly on the AP exam. You'll implement them directly in FRQs and trace through them in multiple choice questions. Know these patterns cold - they're the building blocks for more complex problems.

For multiple choice, expect questions that:

• Give you code implementing these algorithms with small errors
• Ask you to trace through digit extraction or frequency counting
• Test edge cases like empty data or all values being the same

In FRQs:

• FRQ 1 (Methods/Control): Often asks for exactly these algorithms
• FRQ 3 (Array/ArrayList): Finding min/max or computing statistics on arrays
• FRQ 4 (2D Array): These patterns extend to 2D (max in a grid, sum of a row)

Key exam tip: These algorithms are so standard that partial credit is limited. If asked to find a maximum, the graders expect the exact pattern. Practice these until you can write them without thinking. Also, always handle edge cases - the exam loves testing empty arrays or single-element datasets.