2022 AP® Computer Science A FRQ 4 — Data (2D Arrays)

Question

This question involves a two-dimensional array of integers that represents a collection of randomly generated data. A partial declaration of the Data class is shown. You will write two methods of the Data class.

Provided Data Class

public class Data {
    public static final int MAX = /* value not shown */;
    private int[][] grid;
    
    /** Fills all elements of grid with randomly generated values,
     *  as described in part (a)
     *  Precondition: grid is not null.
     *                grid has at least one element. */
    public void repopulate() {
        /* to be implemented in part (a) */
    }
    
    /** Returns the number of columns in grid that are in 
     *  increasing order, as described in part (b)
     *  Precondition: grid is not null.
     *                grid has at least one element. */
    public int countIncreasingCols() {
        /* to be implemented in part (b) */
    }
    
    // There may be instance variables, constructors, and methods 
    // that are not shown.
}

Part (a): Write repopulate Method

Write the repopulate method, which assigns a newly generated random value to each element of grid. Each value is computed to meet all of the following criteria, and all valid values must have an equal chance of being generated:

• The value is between 1 and MAX, inclusive
• The value is divisible by 10
• The value is not divisible by 100

Examples of Valid Values:

If MAX = 200:

• ✅ 10 (divisible by 10, not by 100)
• ✅ 30 (divisible by 10, not by 100)
• ✅ 50 (divisible by 10, not by 100)
• ✅ 70 (divisible by 10, not by 100)
• ✅ 90 (divisible by 10, not by 100)
• ✅ 110 (divisible by 10, not by 100)
• ✅ 130 (divisible by 10, not by 100)
• ✅ 150 (divisible by 10, not by 100)
• ✅ 170 (divisible by 10, not by 100)
• ✅ 190 (divisible by 10, not by 100)

Examples of Invalid Values:

• ❌ 5 (not divisible by 10)
• ❌ 25 (not divisible by 10)
• ❌ 100 (divisible by 100)
• ❌ 200 (divisible by 100)

Part (b): Write countIncreasingCols Method

Write the countIncreasingCols method, which returns the number of columns in grid that are in increasing order.

A column is considered to be in increasing order if the element in each row after the first row is greater than or equal to the element in the previous row. A column with only one row is considered to be in increasing order.

Example 1:

The return value for the following contents of grid is 1, since the first column is in increasing order but the second and third columns are not:

Example 2:

The return value for the following contents of grid is 2, since the first and third columns are in increasing order but the second and fourth columns are not:

Solution & Explanation

Part (a) Solution: repopulate

public void repopulate() {
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            int value;
            
            do {
                value = (int)(Math.random() * MAX) + 1;
            } while (value % 10 != 0 || value % 100 == 0);
            
            grid[r][c] = value;
        }
    }
}

Step-by-Step Explanation:

1. Outer loop (rows): for (int r = 0; r < grid.length; r++)
   • grid.length gives the number of rows
   • Iterates through each row
2. Inner loop (columns): for (int c = 0; c < grid[0].length; c++)
   • grid[0].length gives the number of columns (length of first row)
   • Iterates through each column in the current row
3. Declare value variable: int value;
   • Will hold the randomly generated number
   • Declared outside do-while so it's accessible after the loop
4. Generate random number: value = (int)(Math.random() * MAX) + 1;
   • Math.random() returns a value in range [0.0, 1.0)
   • Multiply by MAX gives range [0.0, MAX)
   • Cast to int gives range [0, MAX-1]
   • Add 1 gives range [1, MAX]
5. Check constraints with do-while: while (value % 10 != 0 || value % 100 == 0)
   • Continue looping while conditions are NOT met
   • value % 10 != 0 → value is NOT divisible by 10 (bad)
   • value % 100 == 0 → value IS divisible by 100 (bad)
   • Loop continues if either condition is true (use ||)
   • Loop stops when value is divisible by 10 AND not divisible by 100
6. Assign to grid: grid[r][c] = value;
   • Once a valid value is found, assign it to the current position

Why do-while Instead of while?

A do-while loop executes the body at least once before checking the condition. This is perfect here because we must generate at least one random number before we can check if it meets the criteria.

Part (b) Solution: countIncreasingCols

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;
}

Step-by-Step Explanation:

1. Initialize counter: int count = 0;
   • Will track the number of increasing columns
2. Outer loop (columns): for (int c = 0; c < grid[0].length; c++)
   • Loop through columns, not rows
   • This is column-wise traversal
3. Boolean flag: boolean increasing = true;
   • Assume column is increasing initially
   • Will be set to false if we find a decrease
   • Reset for each column
4. Inner loop (rows): for (int r = 1; r < grid.length; r++)
   • Start at row 1, not row 0 (we compare with previous row)
   • Iterate through each row in the current column
5. Check increasing order: if (grid[r][c] < grid[r-1][c])
   • Compare current element with previous row's element in same column
   • If current is less than previous, column is NOT increasing
   • Note: We allow equal values (≥ not just >)
6. Set flag to false: increasing = false;
   • Mark this column as not increasing
   • Don't use break — not needed, and AP discourages it
7. Increment count if increasing: if (increasing) { count++; }
   • After checking entire column, if flag is still true, increment counter
8. Return count: return count;
   • Return the total number of increasing columns

Detailed Explanation

Key Concepts Tested

1. 2D Array Structure

A 2D array in Java is an array of arrays:

int[][] grid = {
    {10, 50, 40},   // row 0
    {20, 40, 20},   // row 1
    {30, 50, 30}    // row 2
};

• grid.length → number of rows (3)
• grid[0].length → number of columns (3)
• grid[r][c] → element at row r, column c

2. Math.random() Range Generation

To generate random integers from 1 to MAX:

(int)(Math.random() * MAX) + 1

Breakdown:

• Math.random() → [0.0, 1.0)
• Math.random() * MAX → [0.0, MAX)
• (int)(Math.random() * MAX) → [0, MAX-1]
• (int)(Math.random() * MAX) + 1 → [1, MAX]

3. Modulo Operator for Divisibility

// Check if divisible by 10
value % 10 == 0  // remainder is 0

// Check if NOT divisible by 100
value % 100 != 0  // remainder is not 0

4. do-while vs while Loops

do-while: Executes body at least once, then checks condition

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

while: Checks condition first, then executes body

// Would need to initialize value first
int value = (int)(Math.random() * MAX) + 1;
while (value % 10 != 0 || value % 100 == 0) {
    value = (int)(Math.random() * MAX) + 1;
}

do-while is cleaner for this problem — no duplicate code.

5. Row-wise vs Column-wise Traversal

Row-wise (typical):

for (int r = 0; r < grid.length; r++) {
    for (int c = 0; c < grid[0].length; c++) {
        // process grid[r][c]
    }
}

Column-wise (part b):

for (int c = 0; c < grid[0].length; c++) {
    for (int r = 0; r < grid.length; r++) {
        // process grid[r][c]
    }
}

The order matters! In part (b), we want to check each column completely before moving to the next column.

6. Boolean Flag Pattern

Common pattern for checking a condition across a collection:

1. Assume the condition is true
2. Loop through elements
3. If condition is violated, set flag to false
4. After loop, check flag

Why These Algorithms?

Part (a): The do-while ensures we keep generating random numbers until we get one that meets all criteria. The OR logic (||) means "keep trying if EITHER constraint is broken."

Part (b): The column-wise traversal with boolean flag is the standard pattern for checking if a sequence has a property. We could use break to exit early when we find a decrease, but the AP exam typically doesn't require that optimization.

Common Mistakes to Avoid

Part (a) Common Errors

• ❌ Wrong random range: (int)(Math.random() * MAX) (gives 0 to MAX-1, not 1 to MAX)
• ❌ Using while instead of do-while: Requires duplicate code to initialize value
• ❌ Wrong boolean logic: Using && instead of || in loop condition
• ❌ Inverted condition: while (value % 10 == 0 && value % 100 != 0) (loops when GOOD, not when BAD)
• ❌ Wrong divisibility check: value / 10 == 0 instead of value % 10 == 0
• ❌ Forgetting to assign: Not storing value in grid[r][c]

Part (b) Common Errors

• ❌ Row-wise instead of column-wise: Outer loop for rows, inner for columns (backwards)
• ❌ Starting inner loop at 0: for (int r = 0; ...) causes grid[r-1][c] to fail at r=0
• ❌ Wrong comparison: Using <= instead of < (equal values are allowed)
• ❌ Not resetting flag: Declaring increasing outside the column loop
• ❌ Incrementing count wrong: Incrementing inside inner loop instead of after
• ❌ Array index errors: Using grid[c][r] instead of grid[r][c]
• ❌ Comparing rows instead of columns: grid[r][c] < grid[r][c-1]

General 2D Array Errors

• ❌ Confusing rows and columns: grid.length is rows, grid[0].length is columns
• ❌ Incorrect array access: grid[c][r] when you mean grid[r][c]
• ❌ Jagged array assumption: Using grid[r].length when grid[0].length is safer

Scoring Rubric

Part (a): 4 Points

Part (b): 5 Points

Total: 9 points possible