Suppose you are given an array s[1..n] and a procedure reverse(s, i, j), which…
2000
Suppose you are given an array s[1..n] and a procedure reverse(s, i, j), which reverses the order of elements in s between positions i and j, both inclusive. What does the following sequence do, where 1 <= k <= n?
reverse(s, 1, k);
reverse(s, k + 1, n);
reverse(s, 1, n);
- A.
Rotates s left by k positions
- B.
Leaves s unchanged
- C.
Reverses all elements of s
- D.
None of the above
Attempted by 109 students.
Show answer & explanation
Correct answer: A
The correct answer is: Rotates s left by k positions.
The sequence uses the standard three-reversal algorithm for left rotation.
First, reverse(s, 1, k) reverses the first k elements. Then reverse(s, k + 1, n) reverses the remaining n - k elements. Finally, reverse(s, 1, n) reverses the whole array.
After the final reversal, the second block moves to the front and the first k elements move to the end, with internal order restored.
For example, for [1, 2, 3, 4, 5] and k = 2, the final array is [3, 4, 5, 1, 2].