in Algorithms edited by
5,116 views
23 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
in Algorithms edited by
5.1k views

4 Comments

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 .
2
I think there is a typo in question.
0
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.
0

1 Answer

46 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\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

14 Comments

can u please expla details

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.
0

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.

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

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.
0
Awesome
0

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.

0

Check this picture above. It performs left rotate by k bits. Option A is the correct option

@

0
Answer:

Related questions