Consider the following C-function in which a[n] and b[m] are two sorted…
2006
Consider the following C-function in which a[n] and b[m] are two sorted integer arrays and c[n + m] be another integer array.
C
void xyz(int a[], int b [], int c[])
{
int i, j, k;
i = j = k = O;
while ((i<n) && (j<m))
if (a[i] < b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
}
Which of the following condition(s) hold(s) after the termination of the while loop?
(i) j < m, k = n+j-1, and a[n-1] < b[j] if i = n
(ii) i < n, k = m+i-1, and b[m-1] <= a[i] if j = m
- A.
only (i)
- B.
only (ii)
- C.
either (i) or (ii) but not both
- D.
neither (i) nor (ii)
Attempted by 5 students.
Show answer & explanation
Correct answer: D
Final answer: neither (i) nor (ii). Both statements contain an off-by-one error in the expression for k.
Reasoning:
The while loop merges elements one at a time until one array is exhausted, so when the loop stops exactly one of these holds: i = n (first array exhausted) or j = m (second array exhausted). The other index is strictly less than its length.
If the first array is exhausted (i = n) then j < m. The total number of elements copied into c is k = i + j = n + j (k starts at 0 and increments once per copied element). The last step that made i reach n copied a[n-1], which required a[n-1] < b[j] at that time, so a[n-1] < b[j] holds.
If the second array is exhausted (j = m) then i < n. The total number of elements copied is k = i + j = i + m. The last step that made j reach m copied b[m-1], which required a[i] >= b[m-1], so b[m-1] <= a[i] holds.
The original statements gave k = n + j - 1 and k = m + i - 1, which are off by one. Because of those incorrect k expressions, neither statement (i) nor statement (ii) is fully correct.
Therefore the correct choice is the one that says neither (i) nor (ii).