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).
Author
{"1486bc8": "/users/pagelets/trending_card/?sensual=True"}