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 356 students.
Show answer & explanation
Correct answer: A
Performing the given three reversals for any value of k results in a left rotation of an array of size n by k positions.
Consider the array
S[1…7]=[1 2 3 4 5 6 7]
Here, n=7 and k=2.
After reversing S(1,2):
[2 1 3 4 5 6 7]After reversing S(3,7):
[2 1 7 6 5 4 3]After reversing S(1,7):
[3 4 5 6 7 1 2]
Thus, the array is rotated left by k positions.