Let a be an array containing n integers in increasing order. The following…
2005
Let a be an array containing n integers in increasing order. The following algorithm determines whether there are two distinct numbers in the array whose difference is a specified number S > 0.
C
i = 0;
j = 1;
while (j < n )
{
if (E) j++;
else if (a[j] - a[i] == S) break;
else i++;
}
if (j < n)
printf("yes")
else
printf ("no");
Choose the correct expression for E.
- A.
a[j] - a[i] > S
- B.
a[j] - a[i] < S
- C.
a[i] - a[j] < S
- D.
a[i] - a[j] > S
Attempted by 49 students.
Show answer & explanation
Correct answer: B
Answer: The correct expression for E is a[j] - a[i] < S.
Reasoning:
Because the array is sorted in increasing order, increasing j (moving the larger index forward) can only increase a[j] and thus increase a[j] - a[i].
If the current difference is less than S (a[j] - a[i] < S), we need a larger difference, so incrementing j is the correct action.
If the current difference is greater than S (a[j] - a[i] > S), we need a smaller difference, so increment i to raise the lower value and reduce the difference.
If the difference equals S, the algorithm stops and reports success.
Correctness and complexity:
The two-pointer process maintains i < j and moves one pointer forward each iteration, so it cannot loop indefinitely and will terminate with j = n at worst.
Each pointer moves at most n steps in total, so the time complexity is O(n).