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]
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
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 :
C++
#include <iostream>
using namespace std;
int arr[10000];
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;
}
}
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);
}
}
int main()
{
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
for ( int i = 0; i < 4; i++)
{
fun(arr, i);
cout << ( "[" );
for ( int j = 0; j < 4; j++)
{
cout << (arr[j]) << ", " ;
}
cout << ( "]" );
}
}
|
Java
class GFG{
static int arr[] = new int [ 10000 ];
public 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 ;
}
}
public 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);
}
}
public 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( "]" );
}
}
}
|
Python
def reverse(arr, s, e):
while s < e:
tem = arr[s]
arr[s] = arr[e]
arr[e] = tem
s = s + 1
e = e - 1
def fun(arr, k):
n = len (arr) - 1
v = n - k
if v> = 0 :
reverse(arr, 0 , v)
reverse(arr, v + 1 , n)
reverse(arr, 0 , n)
return arr
arr = [ 1 , 2 , 3 , 4 ]
for i in range ( 0 , len (arr)):
count = 0
p = fun(arr, i)
print (p, end = " " )
|
C#
using System;
class GFG{
static int []arr = new int [10000];
public 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;
}
}
public 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);
}
}
public 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);
Console.Write( "[" );
for ( int j = 0; j < 4; j++)
{
Console.Write(arr[j] + ", " );
}
Console.Write( "]" );
}
}
}
|
Javascript
<script>
arr = Array.from({length: 10000}, (_, i) => 0);
function reverse(arr, s , e)
{
while (s < e)
{
var tem = arr[s];
arr[s] = arr[e];
arr[e] = tem;
s = s + 1;
e = e - 1;
}
}
function fun(arr , k)
{
var n = 4 - 1;
var v = n - k;
if (v >= 0)
{
reverse(arr, 0, v);
reverse(arr, v + 1, n);
reverse(arr, 0, n);
}
}
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
for (i = 0; i < 4; i++)
{
fun(arr, i);
document.write( "[" );
for (j = 0; j < 4; j++)
{
document.write(arr[j] + ", " );
}
document.write( "]<br>" );
}
</script>
|
Output
[1, 2, 3, 4] [4, 1, 2, 3] [2, 3, 4, 1] [3, 4, 1, 2]
Time Complexity: O (N2)
Auxiliary Space: O (1), since no extra space has been taken.
Approach 2: Follow the steps below to solve the problem:
- Initialize the original array arr and its size n.
- Create a new array rotatedArr of size 2 * n and copy the elements of arr into it.
- Generate all possible rotations by iterating over i from 0 to n-1 and printing the bracketed sequence of elements from rotatedArr[i] to rotatedArr[i + n – 1].
- Exit the program.
Below is the implementation of the above approach:
C++
#include <iostream>
#include <vector>
int main()
{
std::vector< int > arr = {1, 2, 3, 4};
int n = arr.size();
std::vector< int > rotatedArr(2 * n);
for ( int i = 0; i < n; i++) {
rotatedArr[i] = arr[i];
rotatedArr[i + n] = arr[i];
}
for ( int i = 0; i < n; i++) {
std::cout << "[" ;
for ( int j = i; j < i + n; j++) {
std::cout << rotatedArr[j];
if (j != i + n - 1)
std::cout << " " ;
}
std::cout << "] " ;
}
return 0;
}
|
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];
for ( int i = 0 ; i < n; i++) {
rotatedArr[i] = arr[i];
rotatedArr[i+n] = arr[i];
}
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( "] " );
}
}
}
|
Python3
arr = [ 1 , 2 , 3 , 4 ]
n = len (arr)
rotatedArr = arr + arr
for i in range (n):
print ( "[" , end = "")
for j in range (i, i + n):
print (rotatedArr[j], end = "")
if j ! = i + n - 1 :
print ( " " , end = "")
print ( "]" , end = " " )
|
C#
using System;
class GFG {
static void Main( string [] args)
{
int [] arr = { 1, 2, 3, 4 };
int n = arr.Length;
int [] rotatedArr = new int [2 * n];
for ( int i = 0; i < n; i++) {
rotatedArr[i] = arr[i];
rotatedArr[i + n] = arr[i];
}
for ( int i = 0; i < n; i++) {
Console.Write( "[" );
for ( int j = i; j < i + n; j++) {
Console.Write(rotatedArr[j]);
if (j != i + n - 1)
Console.Write( " " );
}
Console.Write( "] " );
}
}
}
|
Javascript
function rotateArray(arr) {
const n = arr.length;
const rotatedArr = new Array(2 * n);
for (let i = 0; i < n; i++) {
rotatedArr[i] = arr[i];
rotatedArr[i + n] = arr[i];
}
const allRotations = [];
for (let i = 0; i < n; i++) {
let rotation = [];
for (let j = i; j < i + n; j++) {
rotation.push(rotatedArr[j]);
}
allRotations.push(rotation);
}
return allRotations;
}
const arr = [1, 2, 3, 4];
const result = rotateArray(arr);
result.forEach(rotation => {
console.log( '[ ' + rotation.join( ' ' ) + ' ]' );
});
|
Output
[1 2 3 4] [2 3 4 1] [3 4 1 2] [4 1 2 3]
Time Complexity: O(N2)
Auxiliary Space: O(1)
Contact Us