How to determine the best postcondition in this question?

user_14006942 0
Viewed 61
  1. Consider the following program segment:
/** Precondition: a[0]...a[n-1] is an initialized array of integers, and 0 < n <= a.length. **/
int c = 0;
for (int i = 0; i < n; i++)
  if (a[i] >= 0)
  {
    a[c] = a[i];
    c++;
  }
n = c;

Which is the best postcondition for the segment?

  1. a[0] to a[n-1] has been stripped of all positive integers.
  2. a[0] to a[n-1] has been stripped of all negative integers.
  3. a[0] to a[n-1] has been stripped of all nonnegative integers.
  4. 4a[0] to a[n-1] has been stripped of all occurrences of zero.
  5. The updated value of n is less than or equal to the value of n before execution of the segment.

This is a question on the AP CSA exam. The answer key says that 2. is the answer (it states that 5. is also correct but would not be the "best" postcondition). But I am just thinking: "what if ALL the elements in the initial list are negative numbers?" If that's the case, wouldn't it be impossible to strip away any negative number?

arrays java
2 Answers

"what if ALL the elements in the initial list are negative numbers?" If that's the case, wouldn't it be impossible to strip away any negative number?

I thought so too at first, but note that the end n is updated:

n = c

With that and only negative numbers n would be zero and a[0] to a[n-1] would be an empty set, for which the statement It does not contain negative numbers is true.

Jens_Schauder_666860

Note, that the algorithm is changing the array's values in place, so it really "strips away" negative numbers. It does it by iterating through all elements of array a and moving it to a lower index if it's a non-negative number.

Then at the end, it sets n to the last index of the element which met the criteria (being non-negative). That's why you have n = c; as the last statement.

So statement 2 is true. The new size of the array is always smaller or equal to the original, so statement 5 is also true.

One thing to notice: In Java, you can still reach all elements if you iterate through the original array. Because in Java every array has a fixed length since being initialized. Let's see the following array:

int a[] = {-1,2,3,-4,5,-6,7,8,-9,-10};

So if I iterate using n at the end, I just get the values that meet the criteria:

for (int i = 0; i < n; i++) {
    System.out.print(a[i] + ",");
}

This will print 2,3,5,7,8, but if I iterate through a I get all the values from the end of the array:

for (int e : a) {
    System.out.print(e + ",");
}

Now it will print 2,3,5,7,8,-6,7,8,-9,-10. So this algorithm leaves some garbage behind.

user_83217870
Related