edited by
8,963 views
27 votes
27 votes

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 \leqslant k \leqslant n$:

           reverse (s, 1, k);
           reverse (s, k+1, n);
           reverse (s, 1, n);
  1. Rotates $s$ left by $k$ positions
  2. Leaves $s$ unchanged 
  3. Reverses all elements of $s$
  4. None of the above
edited by

1 Answer

Best answer
52 votes
52 votes

Answer is A.

Effect of the above $3$ reversals for any $K$ is equivalent to left rotation of the array of size $n$ by $k$.

Let , $S[1\ldots7] = \begin{array}{|c|c|c|c|c|c|c|}\hline1&2&3&4&5&6&7\\ \hline\end{array}$
So, $n=7,k = 2$

reverse $(S,1,2)$ we get $[2,1,3,4,5,6,7]$

reverse $(S,3,7)$ we get $[2,1,7,6,5,4,3]$

reverse $(S,1,7)$ we get $[3,4,5,6,7,1,2]$

Hence, option $(A)$ rotates $s$ left by $k$ positions and is correct.

edited by
Answer:

Related questions

79 votes
79 votes
10 answers
3
Kathleen asked Sep 14, 2014
22,583 views
Consider the following functions$f(n) = 3n^{\sqrt{n}}$$g(n) = 2^{\sqrt{n}{\log_{2}n}}$$h(n) = n!$Which of the following is true?$h(n)$ is $O(f(n))$$h(n)$ is $O(g(n))$$g(n...