Suppose you are given an array s[1..n] and a procedure reverse(s, i, j) that…
2000
Suppose you are given an array s[1..n] and a procedure reverse(s, i, j) that reverses the order of the 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);Answer: A. Rotates s left by k positions — ConceptA reversal changes the order inside one contiguous segment. If an array is split into a prefix A and a suffix B, reversing A, then B, and then the…
- A.
Rotates s left by k positions
- B.
Leaves s unchanged
- C.
Reverses all elements of s
- D.
None of the above
Attempted by 536 students.
Show answer & explanation
Correct answer: A
Concept
A reversal changes the order inside one contiguous segment. If an array is split into a prefix A and a suffix B, reversing A, then B, and then the whole array transforms reverse(A) reverse(B) into BA.
This three-reversal identity preserves the internal order of A and B in the final arrangement and uses O(n) time with O(1) extra space when reversal is in place.
Application
Let A = s[1..k] and B = s[k+1..n], so the initial array is AB.
After reverse(s, 1, k), the array is reverse(A)B.
After reverse(s, k + 1, n), the array is reverse(A)reverse(B).
Reversing the whole array gives reverse(reverse(A)reverse(B)) = BA.
Cross-check
For s = [1, 2, 3, 4, 5] and k = 2, the three states are [2, 1, 3, 4, 5], [2, 1, 5, 4, 3], and [3, 4, 5, 1, 2]. The prefix [1, 2] moves to the end without changing its internal order.
Result
Therefore, the sequence rotates s left by k positions.
A video solution is available for this question — log in and enroll to watch it.