GATE CSE 2000 | Question: 2.15

Question

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);

• A. Rotates $s$ left by $k$ positions
• B. Leaves $s$ unchanged 
• C. Reverses all elements of $s$
• D. None of the above

Comments

My point was in the last rev its reversal of 1 ... n the whole list how have you got what you wrote above?? it should be 45123.... how can you do such mistake if it was... :()

---

@sourojyoti

How have you got what you wrote above?' -- Back then, I didn't also understand what was wrong with my thinking, that was leading to a much different answer from others. Thus I took to the comments for help to figure it out.

And thank you so much for your concern, but, I don't think you should invest your time thinking, 'how can you do such a mistake'. Everyone is a struggler here, everyone does mistakes, too silly, or too obvious ones. You just don't need to be bothered about others. If you can help, answer in the comment, politely, much like the others are doing. If you can't help, kindly pass by.

P.S.: And don't respond back to my comment.  This is not a social media thread that is supposed to keep going on. This community is meant for students. UNNECESSARY COMMENTS WILL DISTURB OTHERS. So, kindly keep quiet. 

YOU SAID THINGS IN A RUDE WAY AND YOU KNOW THAT VERY WELL. THUS, I RECTIFIED YOU. JUST KEEP THAT IN MIND. Happy learning!

---

And don't respond back to my comment.  This is not a social media thread that is supposed to keep going on. This community is meant for students. UNNECESSARY COMMENTS WILL DISTURB OTHERS. So, kindly keep quiet. 

Answer 1

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.

Comments

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

@Divyanshu Shukla

---

Left Rotation and Right Rotation of a String - GeeksforGeeks

Answer 2

Ex:

Answer 3

k=4

string s:          3 5 1 9 2 13 7

reverse (s, 1, 4): 9 1 5 3 2 13 7

reverse (s, 5, 7): 9 1 5 3 7 13 2

reverse (s, 1, 7): 2 13 7 3 5 1 9

 

Roation to leftt by one position: 5 1 9 2 13 7 3

Roation to leftt by one position: 1 9 2 13 7 3 5

Roation to leftt by one position: 9 2 13 7 3 5 1

Roation to leftt by one position: 2 13 7 3 5 1 9

TRUE

 

Rotates s by 4 positions from towards L

OPTION C

Comments

HOW

 

---

https://www.geeksforgeeks.org/left-rotation-right-rotation-string-2/

Answer 4

Let array S is [1...k, k+1...n]

reverse(S,1,k): [k...1, k+1...n]

reverse(S, k+1, n]:  [k...1, n...k+1]

reverse(S,1,n): [k+1...n, 1...k]

It's original array left rotate by k positions.

 

Comments

Yes—the answer key chooses A because the sequence generally performs a left rotation by (k) positions.

When (k=n\) a left rotation by  n positions is equivalent to no rotation, so the array happens to remain unchanged. Thus:

• General operation: A
• Special case \(k=n\): unchanged, which is consistent with A.

Answer 5

let array : [ 1 .... k, k+1 .... n ]

1st rev : [ k .... 1, k+1 .... n ]

2nd rev : [ k .... 1, n .... k+1 ]

3rd rev : [ k+1 .... n, 1 .... k ] => clearly k elements shifted to left...