5,116 views

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

Answer is not A .  It is D;

Explanation :: let take array of n < =4 and perform thiz u will get different array ( not option A ) after operation .

And for n>=5

here they illustrated  k is 1<= k <=n

n = 1 2 3 4 5

what if take k==n

it goes invalid for k+1 bcz there is not other element on k+1 location .
I think there is a typo in question.
Answer will be A in any case let us take n=4, and lets assume array is S={1,2,3,4}

lets take k=2.Now:

reverse(s,1,2)→ 2,1,3,4

reverse(s,3,4)→ 2,1,4,3

reverse(s,1,4) → 3,4,1,2

Hence option A is the correct Answer.

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.

rev(s,k+1,n)

rev(s,1,n)
How this rotattion takes place i mean how rev(s,1,7) gives the output 3,4,5,6,7,1,2..Plz explain..am getting doubt here.

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]

It is explaind in the above lines,

see,  reverse(S,1,2) - reverse elements form index 1 to 2 of list S = [1, 2, 3, 4, 5, 6, 7]..

we get S = [2,1,3,4,5,6,7].

Now reverse(S,3,7)  - reverse elements from index 3 to 7 of lis S = [2,1,3,4,5,6,7].

we get S = [2,1,7,6,5,4,3].

Now reverse(S,1,7)  - reverse elements from index 1 to 7 of lis S =[2,1,7,6,5,4,3].

we get S = [ 3,4,5,6,7,1,2 ]

now compare this final list([ 3,4,5,6,7,1,2 ]) with the initial list ( [1,2,3,4,5,6,7]), you will see the rotation of elements towards left.

example- initially 3 was at index 3 and now it is at index 1.

initially 1 was at indext 1 and now it is at index 6. { don't confuse with its a right rotation with k= 5}.

similaly you can verify other elements shift.

thanks..very nice explanation
no D is right answer .

the answer a is true for only some array

implement on

1 2 3 4  here n =4 k=3

final u will get 4 1 2 3

it work on n >=5
^you have got correct final array but you did not analyse that it is also rotated 3 times towards left.

hope you get the point..
i got but what if we take n==k?
there is typing mistake in the question..i have checked it is k<n not k<=n, so the final answer is A
Take array is 1,5,7,8 n=4,k=3                            Reverse (s, 1,3) so array becomes 7,5,1,8   Reverse (s, 4,4) no change remain same 1,5,7,8

Reverse (s, 1,4) array is now 8,5,7,1

If you left rotate 3 times then it will be look like

If I am wrong plz kindly correct me.
Awesome

for n=3 and k=2 Let s be

 2 1 3

after reverse(s,1,2)

 1 2 3

after reverse(s,3,3)

 1 2 3

after reverse(s,1,3)

 3 2 1

So array shift by only a single position. Hence D is correct. Check this picture above. It performs left rotate by k bits. Option A is the correct option