2k 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
edited | 2k views
+1
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 .
0
I think there is a typo in question.

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.

edited
0

rev(s,k+1,n)

rev(s,1,n)
0
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.
+10

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.

0
thanks..very nice explanation
0
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
0
^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..
0
i got but what if we take n==k?
0
there is typing mistake in the question..i have checked it is k<n not k<=n, so the final answer is A
0
0
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.

1
2