Data: 2022 FRQ 4

Filling and scanning a two-dimensional array of numbers is the focus of this AP Computer Science A free-response question — first generating random values that satisfy several rules at once, then traversing the grid column by column to check a pattern.

What This FRQ Tests

• AP CSA units: Unit 8 (2D Array) and Unit 4 (Iteration)
• Core skill: nested loops for both filling and traversing a 2D array (grid.length for rows, grid[r].length for columns)
• Secondary skill: generating random values within a range that also satisfy extra divisibility constraints, without skewing the odds
• Official category: "2D Array" — always FRQ 4 on the AP CSA exam

The Setup

• Data holds:
  • private int[][] grid — a two-dimensional array of ints
  • public static final int MAX — a constant upper bound (its exact value isn't given, and doesn't need to be)
• You're asked to write two methods:
  • repopulate() — fills every element of grid with a new random value
  • countIncreasingCols() — returns how many columns are "increasing" top to bottom

Part (a): Writing repopulate()

The Rule, Broken Down

Every generated value must satisfy all three of these at once:

1. Between 1 and MAX, inclusive
2. Divisible by 10
3. Not divisible by 100

And critically: every value that satisfies all three rules must have an equal chance of being generated — the method can't skew the odds toward some valid values over others.

Step-by-Step Approach

1. Figure out how many multiples of 10 exist between 1 and MAX — that's MAX / 10.
2. Generate a random whole number from 1 to MAX / 10 (call it the "multiplier"), and multiply it by 10. This gives a random multiple of 10 in range, with every multiple equally likely.
3. Check whether that value is divisible by 100 (i.e., is it a "round hundred" like 100, 200, 300...). If so, it's invalid — throw it away and generate again.
4. Repeat step 2–3 for every position in the grid, using nested loops for rows and columns.

A do-while loop is the natural tool for step 2–3: you always want to generate a candidate value at least once, and only loop back around if that candidate turns out to be invalid.

The Code

public void repopulate()
{
    for (int r = 0; r < grid.length; r++)
    {
        for (int c = 0; c < grid[r].length; c++)
        {
            int value;

            do
            {
                int multiplesOfTen = MAX / 10;
                int randomMultiple = (int) (Math.random() * multiplesOfTen) + 1;
                value = randomMultiple * 10;
            }
            while (value % 100 == 0);

            grid[r][c] = value;
        }
    }
}

Why Each Piece Matters

• Math.random() returns a double from 0.0 up to (but never including) 1.0.
• Math.random() * multiplesOfTen scales that into the range [0.0, multiplesOfTen).
• (int) (...) truncates to a whole number from 0 to multiplesOfTen - 1.
• + 1 shifts that range to 1 through multiplesOfTen — every integer in that range is equally likely, since truncation of a uniformly-distributed double lands on each integer with equal probability.
• randomMultiple * 10 converts "the 1st, 2nd, 3rd... multiple of ten" into the actual values 10, 20, 30, ..., MAX.
• while (value % 100 == 0) rejects anything divisible by 100 and loops back — because rejected values are simply discarded and re-rolled (not adjusted or mapped to something else), every remaining valid value keeps its original equal probability.

Why Rejection Sampling (Not Math Tricks) Is the Safer Approach

• It would be possible to compute a formula that skips "round hundreds" directly (e.g., generating a digit 1-9 for the tens place and a separate number for the hundreds place), but that's easy to get subtly wrong — and if the arithmetic isn't careful, it can accidentally make some valid values more likely than others.
• A do-while "regenerate until valid" loop is simple to reason about and easy to verify: every path through the loop either produces a valid value, or throws away an invalid one and tries again — nothing in between.

Common Mistakes to Avoid

• Using a while loop instead of do-while. A regular while loop needs the candidate value initialized before the check, and would need duplicate generation code before and inside the loop. do-while avoids that duplication cleanly.
• Checking value % 100 == 0 before multiplying by 10. The check has to run on the final candidate value, not on the raw random multiplier.
• Off-by-one on the multiplier's range. Forgetting the + 1 would allow a multiplier of 0, producing a value of 0 — outside the required 1 to MAX range.
• Trying to "fix" an invalid value instead of regenerating it (e.g., adding 10 to any round-hundred result). This breaks the "equal chance" requirement, since it makes the next multiple of ten twice as likely to appear.

Part (b): Writing countIncreasingCols()

The Rule, Broken Down

• A column is "increasing" if every row after the first is greater than or equal to the row directly above it, in that same column.
• A column with only one row automatically counts as increasing (there's nothing to compare it against).
• Count how many of the grid's columns meet this rule.

Step-by-Step Approach

1. Loop over every column index.
2. For each column, assume it's increasing until proven otherwise (boolean increasing = true).
3. Loop down that column, starting at row 1 (not row 0 — there's no row above row 0 to compare against).
4. At each row, compare the current value to the value directly above it. If it's smaller, the column isn't increasing — flip the flag to false (and let the inner loop keep running; there's no need to stop early).
5. After the inner loop finishes, if the flag is still true, increment the count.
6. After the outer loop finishes, return the count.

The Code

public int countIncreasingCols()
{
    int count = 0;

    for (int c = 0; c < grid[0].length; c++)
    {
        boolean increasing = true;

        for (int r = 1; r < grid.length; r++)
        {
            if (grid[r][c] < grid[r - 1][c])
            {
                increasing = false;
            }
        }

        if (increasing)
        {
            count++;
        }
    }

    return count;
}

Why Each Piece Matters

• grid[0].length gives the number of columns — the length of any one row. (grid.length gives the number of rows instead — mixing these up is one of the most common 2D array bugs.)
• The inner loop starts at r = 1, not 0. Row 0 has no row above it, so there's nothing valid to compare it to.
• increasing starts true and only ever flips to false. This correctly handles the "a single-row column is automatically increasing" rule — if the inner loop finds zero violations (including the case where there's only one row and the loop body never runs at all), the flag stays true.
• grid[r][c] < grid[r - 1][c] — note both indices share the same column c; only the row index changes between the current and previous positions.

Tracing the Example

Using the first example from the question:

Result: count ends at 1, matching the question's expected answer.

Common Mistakes to Avoid

• Swapping grid.length and grid[0].length. This is the classic 2D array bug — always double check which one represents rows and which represents columns.
• Starting the inner loop at r = 0 and comparing grid[0][c] to grid[-1][c] — this doesn't just give the wrong answer, it throws an ArrayIndexOutOfBoundsException.
• Using break to exit the inner loop early after finding one violation. It's not wrong, exactly (the answer would still be correct), but it adds unnecessary complexity — letting the loop finish naturally is simpler to write correctly under exam time pressure.
• Checking the wrong direction — grid[r][c] > grid[r-1][c] instead of <. The rule is "greater than or equal to the row above," so the violation condition is strictly "less than."

Key Takeaways

• 2D array traversal almost always means nested loops — outer loop for one dimension, inner loop for the other — and getting grid.length vs. grid[0].length right is essential.
• "Equal chance of being generated" is a strong hint toward a rejection-sampling do-while loop, not a clever formula.
• A boolean flag that starts true and can only flip to false is the standard pattern for "check that nothing in this sequence violates a rule."