DiverseArray Solution

Got to be honest about this one. When I saw that the first part of the first free response question on the 2015 AP Computer Science exam was to sum up an array I laughed a little bit. Summing up an array is one of the first labs that we do during the arrays unit, and iterating through list structures is something that we do a lot in class. I was pretty sure that all of my students got the points for part A on this one.

The task was to determine if a 2 dimensional array was “diverse,” which they defined as a matrix where no two rows have the same sum.  Part A was a helper for part B, which was in turn a helper for part C.

Part A

The arraySum method takes an integer array called arr and returns the sum.

Here are three different solutions to arraySum. The first is a for each loop, the second a standard for loop, and the third is a while loop.

public static int arraySum( int[] arr ) {
    int s = 0;
    for (int n: arr)
        s += n;
    return s;
}

public static int arraySum( int[] arr ) {
  int s = 0;
  for (int i=; i<arr.length; i++) {
    s += arr[i]
  }
  return s;
}

public static int arraySum( int[] arr ) {
  int s = 0;
  int pos = 0;
  while (pos < arr.length) {
    s += arr[pos];
    pos++;
  }
  return s;
}

I don’t remember how many points this part was on the rubric, but I’m assuming that most students got all the points available.

Part B

Next you’re given a 2 dimensional int array called arr2D and have to return a 1 dimensional integer array with the sums from each row. Fortunately we’ve already made a method that sums an array, and we know that each row in a matrix is an array.

public static int[] rowSums( int[][] arr2D ) {
    int[] out = new int[arr2D.length];
    for (int i=0; i<arr2D.length; i++)
        out[i] = arraySum(arr2D[i]); 
    return out; 
}

If you don’t know that each row is just a normal array this one could have been a bit confusing.

First we make an array that’s the same length as the number of rows in arr2D. Then we go through each row, calculate the sum using the arraySum method from part A, and store that sum in the corresponding element in our returned array out.

This one could have also been done with different types of loops, but I’m guessing that most people used for loops.

Part C

And the last part was the namesake method isDiverse where you had to determine if arr2D was diverse. The problem defined diverse as a matrix where no two rows had the same sum.

public static boolean isDiverse( int[][] arr2D ) {
    /* To be implemented in Part C */
    int[] check = rowSums(arr2D);
    for (int i=0; i<check.length; i++) {
        for (int j=i+1; j<check.length; j++) {
            if (check[i] == check[j])
                return false; 
        }
    }
    return true; 
}

Since we’ve already written the rowSums method to get the sums of each individual row we’re going to use that to create check which contains those sums.

Next we’ll go through check and look for duplicates. Starting at position 0 we compare that spot to each element that follows it in check. If they match, we found a duplicate and the matrix is not diverse. We only have to check elements that come after because anything earlier in the array would have already been checked. For example, there’s no reason to compare position 2 to position 0 when we’ve already compared position 0 to position 2.

If our code gets all the way through the loops without returning false then we know that there weren’t any duplicates and can return true.

 

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *