The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+19 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
asked in Algorithms by Veteran (52k points)
edited by | 2k views
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.

1 Answer

+33 votes
Best answer

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......7]$

1 2 3 4 5 6 7

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.

answered by Active (3.3k points)
edited by
can u please expla details


How this rotattion takes place i mean how rev(s,1,7) gives the output 3,4,5,6,7,1,2..Plz 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
Answer is D not 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

1,5,7,8-----5,7,8,1-----7,8,5,1-----8,1,5,7(different from final answer 8,5,7,1)

So answer D is correct.

If I am wrong plz kindly correct me.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,548 questions
54,174 answers
71,129 users