Loop Invariant for Array Comparison
Consider the following countCommon method, which is intended to count the number of common elements between two sorted integer arrays.
/** Counts the number of common elements between arrays v and w.
* Precondition:
* - v is an array of int sorted in increasing order
* - w is an array of int sorted in increasing order
* - N is the number of elements in array v
* - M is the number of elements in array w
* - v[0] < v[1] < ... < v[N-1] and w[0] < w[1] < ... < w[M-1]. */
public static int countCommon(int[] v, int[] w, int N, int M) {
int vIndex = 0, wIndex = 0, count = 0;
while (vIndex < N && wIndex < M) {
if (v[vIndex] == w[wIndex]) {
count++;
vIndex++;
wIndex++;
} else if (v[vIndex] < w[wIndex]) {
vIndex++;
} else {
wIndex++;
}
}
return count;
}
Which of the following assertions is true after each complete iteration of the while loop?
A
vIndex and wIndex are pointing to the same positions in their respective arrays.
B
count equals the total number of elements compared so far.
C
All elements in v[0…vIndex-1] and w[0…wIndex] have been compared
D
count equals the number of common elements found so far.
Question Leaderboard
Not enough data yet to show leaderboard.
APFIVE