Rotation of the array means that each element is shifted right or left by one index. In case of right rotation the last element of the array is moved to the first place. For example
Input : Given array A = [3, 8, 9, 7, 6] and K = 3 Output: Function should return [9, 7, 6, 3, 8] Explanation: 'K' means rotate the array right by 'K' times
The trick here is the modulo operation. If you notice the rotated arrays, its like the starting point for the rotated array is actually some index i in the original array. This index i can be determined by the number K which represents the number of rotations we want to perform on the given array and then return the result.
// Function to rotate the array A by K times int* rotation(int *A, int size, int K) { int *ret = new int[size]; if (size == 1) { return A; } for (int i = 0; i < size; i++) { ret[(i + K) % size] = A[i]; } return ret; }
If we want to shift an element K times we can calculate the new index by using (index + K) % size
. The modulo operator returns the reminder of the division between two numbers. So if we have an array with 10 elements, and we want to shift the index 3, 5 times if we do it manually we can figure out that the new index should be 8. But lets say that the array has 5 elements instead of 10 then, we know that we need to shift the array to position 3, if you do it one step at a time you can verify that it’s so.
3 + 5 = 8 8 % 5 = 3