Given an integer array arr[] of size N, the task is to print all possible rotations of the array.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: {1, 2, 3, 4}, {4, 1, 2, 3}, {3, 4, 1, 2}, {2, 3, 4, 1}
Explanation:
Initial arr[] = {1, 2, 3, 4}
After first rotation arr[] = {4, 1, 2, 3}
After second rotation arr[] = {3, 4, 1, 2}
After third rotation arr[] = {2, 3, 4, 1}
After fourth rotation, arr[] returns to its original form.Input: arr[] = [1]
Output: [1]
Approach 1:
Follow the steps below to solve the problem:
- Generate all possible rotations of the array, by performing a left rotation of the array one by one.
- Print all possible rotations of the array until the same rotation of array is encountered.
Below is the implementation of the above approach :
Java
// Java program to print// all possible rotations// of the given arrayclass GFG{ // Global declaration of arraystatic int arr[] = new int[10000];// Function to reverse array// between indices s and epublic static void reverse(int arr[], int s, int e){ while(s < e) { int tem = arr[s]; arr[s] = arr[e]; arr[e] = tem; s = s + 1; e = e - 1; }}// Function to generate all// possible rotations of arraypublic static void fun(int arr[], int k){ int n = 4 - 1; int v = n - k; if (v >= 0) { reverse(arr, 0, v); reverse(arr, v + 1, n); reverse(arr, 0, n); }}// Driver codepublic static void main(String args[]){ arr[0] = 1; arr[1] = 2; arr[2] = 3; arr[3] = 4; for(int i = 0; i < 4; i++) { fun(arr, i); System.out.print("["); for(int j = 0; j < 4; j++) { System.out.print(arr[j] + ", "); } System.out.print("]"); }}}// This code is contributed by gk74533 |
[1, 2, 3, 4] [4, 1, 2, 3] [2, 3, 4, 1] [3, 4, 1, 2]
Time Complexity: O (N2)
Auxiliary Space: O (1)
Approach 2: Follow the steps below to solve the problem:
- Create an integer array arr and initialize it with some values.
- Find the length of the array arr using the length property.
- Create a new integer array rotatedArr with twice the length of arr.
- Copy the elements of arr twice into rotatedArr, so that the first half of rotatedArr contains the elements of arr, and the second half contains the same elements of arr.
- Iterate over the indices from 0 to n and generate all possible rotations of arr using rotatedArr. For each iteration, print the sub-array starting from the current index and having the length equal to the length of the input array.
Below is the implementation of the above approach:
Java
public class GFG { public static void main(String[] args) { int[] arr = {1, 2, 3, 4}; int n = arr.length; int[] rotatedArr = new int[2*n]; // Copy the array twice into the rotatedArr for (int i = 0; i < n; i++) { rotatedArr[i] = arr[i]; rotatedArr[i+n] = arr[i]; } // Nikunj Sonigara // Generate all possible rotations for (int i = 0; i < n; i++) { System.out.print("["); for (int j = i; j < i+n; j++) { System.out.print(rotatedArr[j]); if(j != i+n-1) System.out.print(" "); } System.out.print("] "); } }} |
[1 2 3 4] [2 3 4 1] [3 4 1 2] [4 1 2 3]
Time Complexity: O(N2)
Auxiliary Space: O(N)
Please refer complete article on Print all possible rotations of a given Array for more details!
