© Parineeth M R

** Question 22. Rotate an array by k times**

Consider the array {10, 20, 30, 40, 50}. Suppose we rotate the array once, we have to move the elements 10, 20, 30, 40 right by 1 position and move the last element 50 to the beginning to get {50, 10, 20, 30, 40}. So if we have an array of size n, then for 1 rotate operation we will need n moves. If we rotate the array k times then there will be k*n moves. There is a faster method for rotating an array. Let the array be A = {10, 20, 30, 40, 50} and the number of rotations k = 2. The procedure is:

1. Reverse the entire array. So we get {50, 40, 30, 20, 10}

2. Reverse the array in the region 0 to k -1. If k = 2, we reverse the region A[0] to A[1]. So we get the array {40, 50, 30, 20, 10}

3. Finally reverse the array in the region k to n-1 where n is the length of the array. If k=2, we reverse the region A[2] to A[4]. So we get the required result {40, 50, 10, 20, 30}.

With this technique, we always need 2*n moves irrespective of the value of k.

## C/C++

/*Main function to rotate a 1 dimensional array a: array which should be rotated. length: number of elements in the array. Should be > 0 num_rotations: how many times to rotate the array. Should be >= 0 */ void rotate_array(int a[], int length, int num_rotations) { /*Suppose an array has a length of 5, every time we rotate by 5 locations, we end up with the same array. So obtain num_rotations value from 0 to length - 1*/ num_rotations = num_rotations % length; if (num_rotations == 0) return; reverse_array(a, 0, length - 1); reverse_array(a, 0, num_rotations - 1); reverse_array(a, num_rotations, length - 1); }

## Java

/*Main function to rotate a 1 dimensional array a: array which should be rotated. numRotations: how many times to rotate the array. Should be >= 0 */ public static void rotateArray(int[] a, int numRotations) { int length = a.length; if (length == 0) return; /*Suppose an array has a length of 5, every time we rotate by 5 locations, we end up with the same array. So obtain numRotations value from 0 to length - 1*/ numRotations = numRotations % length; if (numRotations == 0) return; reverseArray(a, 0, length - 1); reverseArray(a, 0, numRotations - 1); reverseArray(a, numRotations, length - 1); }

## Python

#Main function to rotate a 1 dimensional list #a: list which should be rotated. #num_rotations: how many times to rotate the list. Should be >= 0 def rotate_list(a, num_rotations) : length = len(a) if (length == 0): return #Suppose a list has a length of 5, every time we rotate by #5 locations, we end up with the same list. So obtain num_rotations #value from 0 to length - 1 num_rotations = num_rotations % length if (num_rotations == 0): return reverse_list(a, 0, length - 1) reverse_list(a, 0, num_rotations - 1) reverse_list(a, num_rotations, length - 1) #Helper function which reverses a list in region (low, high) #a: list which needs to be reversed #low: lower index of region to be reversed #high: higher index of region to be reversed def reverse_list(a, low, high) : while (low < high) : a[low], a[high] = a[high], a[low] low += 1 high = high - 1