Array Rotation

Lets we have an array arr[ ] , size of array n and we have to rotate it by d elements.rotate(arr[], d, n)
{reverse(arr[], 1, d) ;reverse(arr[], d + 1, n);reverse(arr[], l, n);}Let AB are the two parts of the input array where A = arr[0..d-1] and B = arr[d..n-1].The idea of the algorithm is:Reverse A to get ArB. /Ar is reverse of A/Reverse B to get ArBr. /Br is reverse of B/Reverse all to get (ArBr) r = BA.For arr[] = [1, 2, 3, 4, 5, 6, 7], d =2 and n = 7
A = [1, 2] and B = [3, 4, 5, 6, 7]Reverse A, we get ArB = [2, 1, 3, 4, 5, 6, 7]Reverse B, we get ArBr = [2, 1, 7, 6, 5, 4, 3]Reverse all, we get (ArBr)r = [3, 4, 5, 6, 7, 1, 2]Time complexity for above algorithm will be O(n).

News Reporter

Leave a Reply

Your email address will not be published. Required fields are marked *