Given an array, right rotate it by k elements.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} k = 3 Output: 8 9 10 1 2 3 4 5 6 7 Input: arr[] = {121, 232, 33, 43 ,5} k = 2 Output: 43 5 121 232 33
Note : In the below solution, k is assumed to be smaller than or equal to n. We can easily modify the solutions to handle larger k values by doing k = k % n
Algorithm:
rotate(arr[], d, n) reverseArray(arr[], 0, n-1) ; reverse(arr[], 0, d-1); reverse(arr[], d, n-1);
Below is the implementation of above approach:
- JAVA
// Java program for right rotation of
// an array (Reversal Algorithm)
import
java.io.*;
class
GFG
{
// Function to reverse arr[]
// from index start to end
static
void
reverseArray(
int
arr[],
int
start,
int
end)
{
while
(start < end)
{
int
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
// Function to right rotate
// arr[] of size n by d
static
void
rightRotate(
int
arr[],
int
d,
int
n)
{
reverseArray(arr,
0
, n -
1
);
reverseArray(arr,
0
, d -
1
);
reverseArray(arr, d, n -
1
);
}
// Function to print an array
static
void
printArray(
int
arr[],
int
size)
{
for
(
int
i =
0
; i < size; i++)
System.out.print(arr[i] +
" "
);
}
public
static
void
main (String[] args)
{
int
arr[] = {
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
,
10
};
int
n = arr.length;
int
k =
3
;
rightRotate(arr, k, n);
printArray(arr, n);
}
}
Output:
8 9 10 1 2 3 4 5 6 7