The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
985 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
asked in Algorithms by Veteran (68.9k points)
edited by | 985 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 .

1 Answer

+28 votes
Best answer

Answer is A.

Effect of the above $3$ reversal 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$ position is correct

 

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

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
Answer is D not A.


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

32,693 questions
39,293 answers
110,105 comments
36,700 users