Program to cyclically rotate an array by one
Given an array, the task is to cyclically rotate the array clockwise by one time.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}
Output: arr[] = {5, 1, 2, 3, 4}Input: arr[] = {2, 3, 4, 5, 1}
Output: {1, 2, 3, 4, 5}
Approach 1: To solve the problem follow the below idea:
Assign every element with its previous element and first element with the last element .
Illustrations:
Consider an array: arr[] = {1, 2, 3, 4, 5}
- Initialize last element in variable ‘last_el’ that is 5
- Then, iterate from n-1 to 1 and assign arr[i] = arr[i-1]
- arr[4] = arr[3]
- arr[ ] = {1, 2, 3, 4, 4}
- arr[3] = arr[2]
- arr[ ] = {1, 2, 3, 3, 4}
- arr[2] = arr[1]
- arr[ ] = {1, 2, 2, 3, 4}
- arr[1] = arr[0]
- arr[ ] = {1, 1, 2, 3, 4}
- Assign arr[0] = last_el
- arr[0] = 5
- arr[ ] = {5, 1, 2, 3, 4}
- Thus the required array will be {5, 1, 2, 3, 4}
Follow the steps to solve the problem:
- Store the last element in any temp variable
- Shift every element one position ahead
- Assign first value = last value (stored in temp variable).
Below is the implementation for the above approach:
C++14
// C++ code for program // to cyclically rotate // an array by one #include <iostream> using namespace std; void rotate( int arr[], int n) { // store the last element in a variable int last_el = arr[n - 1]; // assign every value by its predecessor for ( int i = n - 1; i > 0; i--) { arr[i] = arr[i - 1]; } // first element will be assigned by last element arr[0] = last_el; } // Driver code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof (arr) / sizeof (arr[0]); // Printing initial array cout << "Given array is \n" ; for ( int i = 0; i < n; i++) cout << arr[i] << ' ' ; // Calling rotate function rotate(arr, n); // Printing rotated array cout << "\nRotated array is\n" ; for ( int i = 0; i < n; i++) cout << arr[i] << ' ' ; return 0; } // This code is contributed by jit_t |
C
// C code for program // to cyclically rotate // an array by one #include <stdio.h> void rotate( int arr[], int n) { // store the last element in a variable int last_el = arr[n - 1]; for ( int i = n - 1; i > 0; i--) arr[i] = arr[i - 1]; // assign the last element to first element arr[0] = last_el; } int main() { int arr[] = { 1, 2, 3, 4, 5 }, i; int n = sizeof (arr) / sizeof (arr[0]); printf ( "Given array is\n" ); for (i = 0; i < n; i++) printf ( "%d " , arr[i]); // Function Call rotate(arr, n); printf ( "\nRotated array is\n" ); for (i = 0; i < n; i++) printf ( "%d " , arr[i]); return 0; } |
Java
// Java code for program // to cyclically rotate // an array by one import java.util.Arrays; public class Test { static int arr[] = new int [] { 1 , 2 , 3 , 4 , 5 }; // Method for rotation static void rotate() { int last_el = arr[arr.length - 1 ], i; for (i = arr.length - 1 ; i > 0 ; i--) arr[i] = arr[i - 1 ]; arr[ 0 ] = last_el; } /* Driver program */ public static void main(String[] args) { System.out.println( "Given Array is" ); System.out.println(Arrays.toString(arr)); // Function Call rotate(); System.out.println( "Rotated Array is" ); System.out.println(Arrays.toString(arr)); } } |
Python3
# Python3 code for program to # cyclically rotate an array by one # Method for rotation def rotate(arr, n): last_el = arr[n - 1 ] for i in range (n - 1 , 0 , - 1 ): arr[i] = arr[i - 1 ] arr[ 0 ] = last_el # Driver function arr = [ 1 , 2 , 3 , 4 , 5 ] n = len (arr) print ( "Given array is" ) for i in range ( 0 , n): print (arr[i], end = ' ' ) rotate(arr, n) print ( "\nRotated array is" ) for i in range ( 0 , n): print (arr[i], end = ' ' ) # This article is contributed # by saloni1297 |
C#
// C# code for program to cyclically // rotate an array by one using System; public class Test { static int [] arr = new int [] { 1, 2, 3, 4, 5 }; // Method for rotation static void rotate() { int last_el = arr[arr.Length - 1], i; for (i = arr.Length - 1; i > 0; i--) arr[i] = arr[i - 1]; arr[0] = last_el; } // Driver Code public static void Main() { Console.WriteLine( "Given Array is" ); string Original_array = string .Join( " " , arr); Console.WriteLine(Original_array); // Function Call rotate(); Console.WriteLine( "Rotated Array is" ); string Rotated_array = string .Join( " " , arr); Console.WriteLine(Rotated_array); } } // This code is contributed by vt_m. |
Javascript
<script> // JavaScript code for program // to cyclically rotate // an array by one function rotate(arr, n) { var last_el = arr[n-1], i; for (i = n-1; i > 0; i--) arr[i] = arr[i-1]; arr[0] = last_el; } var arr = [1, 2, 3, 4, 5]; var n = arr.length; document.write( "Given array is <br>" ); for ( var i = 0; i< n; i++) document.write(arr[i] + " " ); rotate(arr, n); document.write( "<br>Rotated array is <br>" ); for ( var i = 0; i < n; i++) document.write(arr[i] + " " ); </script> |
PHP
<?php // PHP code for program // to cyclically rotate // an array by one function rotate(& $arr , $n ) { $last_el = $arr [ $n - 1]; for ( $i = $n - 1; $i > 0; $i --) $arr [ $i ] = $arr [ $i - 1]; $arr [0] = $last_el ; } // Driver code $arr = array (1, 2, 3, 4, 5); $n = sizeof( $arr ); echo "Given array is \n" ; for ( $i = 0; $i < $n ; $i ++) echo $arr [ $i ] . " " ; rotate( $arr , $n ); echo "\nRotated array is\n" ; for ( $i = 0; $i < $n ; $i ++) echo $arr [ $i ] . " " ; // This code is contributed // by ChitraNayal ?> |
Given array is 1 2 3 4 5 Rotated array is 5 1 2 3 4
Time Complexity: O(n), as we need to iterate through all the elements. Where n is the number of elements in the array.
Auxiliary Space: O(1), as we are using constant space.
Approach 2: To solve the problem follow the below idea:
We can use two pointers, As we know in cyclic rotation we will bring last element to first and shift rest in forward direction, we can do this by swapping every element with last element till we get to the last point.
Follow the steps to solve the problem:
- Take two pointers i and j which point to first and last element of array respectively.
- Start swapping arr[i] and arr[j] and keep j fixed and i moving towards j.
- Repeat above step till i is not equal to j.
Below is the implementation for the above idea:
C++14
// C++ code for the above approach: #include <iostream> using namespace std; void rotate( int arr[], int n) { // i and j pointing to first and last // element respectively int i = 0, j = n - 1; while (i != j) { swap(arr[i], arr[j]); i++; } } // Driver code int main() { int arr[] = { 1, 2, 3, 4, 5 }, i; int n = sizeof (arr) / sizeof (arr[0]); // Function Call cout << "Given array is \n" ; for (i = 0; i < n; i++) cout << arr[i] << " " ; rotate(arr, n); cout << "\nRotated array is\n" ; for (i = 0; i < n; i++) cout << arr[i] << " " ; return 0; } |
C
#include <stdio.h> void swap( int * x, int * y) { int temp = *x; *x = *y; *y = temp; } void rotate( int arr[], int n) { int i = 0, j = n - 1; while (i != j) { swap(&arr[i], &arr[j]); i++; } } int main() { int arr[] = { 1, 2, 3, 4, 5 }, i; int n = sizeof (arr) / sizeof (arr[0]); printf ( "Given array is\n" ); for (i = 0; i < n; i++) printf ( "%d " , arr[i]); rotate(arr, n); printf ( "\nRotated array is\n" ); for (i = 0; i < n; i++) printf ( "%d " , arr[i]); return 0; } |
Java
import java.util.Arrays; public class Test { static int arr[] = new int [] { 1 , 2 , 3 , 4 , 5 }; static void rotate() { int i = 0 , j = arr.length - 1 ; while (i != j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; } } /* Driver program */ public static void main(String[] args) { System.out.println( "Given Array is" ); System.out.println(Arrays.toString(arr)); rotate(); System.out.println( "Rotated Array is" ); System.out.println(Arrays.toString(arr)); } } |
Python3
def rotate(arr, n): i = 0 j = n - 1 while i ! = j: arr[i], arr[j] = arr[j], arr[i] i = i + 1 pass # Driver function arr = [ 1 , 2 , 3 , 4 , 5 ] n = len (arr) print ( "Given array is" ) for i in range ( 0 , n): print (arr[i], end = ' ' ) rotate(arr, n) print ( "\nRotated array is" ) for i in range ( 0 , n): print (arr[i], end = ' ' ) |
C#
// C# code for program to cyclically // rotate an array by one using System; class GFG { static int [] arr = new int [] { 1, 2, 3, 4, 5 }; // Method for rotation static void rotate() { int n = arr[arr.Length - 1]; // i and j pointing to first and // last element respectively int i = 0, j = n - 1; while (i != j) { { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } i++; } } // Driver Code public static void Main() { Console.WriteLine( "Given Array is" ); string Original_array = string .Join( " " , arr); Console.WriteLine(Original_array); rotate(); Console.WriteLine( "Rotated Array is" ); string Rotated_array = string .Join( " " , arr); Console.WriteLine(Rotated_array); } } // This code is contributed by annianni |
Javascript
<script> // JavaScript code for program // to cyclically rotate // an array by one using pointers i,j function rotate(arr, n){ var i = 0 var j = n-1 while (i != j){ let temp; temp = arr[i]; arr[i] = arr[j]; arr[j]= temp; i =i+1 } } var arr = [1, 2, 3, 4, 5]; var n = arr.length; document.write( "Given array is <br>" ); for ( var i = 0; i< n; i++) document.write(arr[i] + " " ); rotate(arr, n); document.write( "<br>Rotated array is <br>" ); for ( var i = 0; i < n; i++) document.write(arr[i] + " " ); </script> |
Given array is 1 2 3 4 5 Rotated array is 5 1 2 3 4
Time Complexity: O(n), as we need to iterate through all the elements. Where n is the number of elements in the array.
Auxiliary Space: O(1), as we are using constant space.
Approach 3: To solve the problem follow the below idea:
We can use Reversal Algorithm also , reverse first n-1 elements and then whole array which will result into one right rotation.
Follow the steps to solve the problem:
- Reverse the array two times.
- First time we will reverse the first n-1(n=size of array) elements.
- Finally, we will get our rotated array by reversing the entire array.
Below is the implementation for the above idea:
C++14
// C++ program to cyclically rotate an array by one #include <iostream> using namespace std; void rotate( int arr[], int n, int k) { // Reverse the first n-1 terms int i, j; for (i = 0, j = n - k - 1; i < j; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Reverse the entire array for (i = 0, j = n - 1; i < j; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int main() { int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 1; // No. of rotations int i, j; cout << "Given array is \n" ; for (i = 0; i < n; i++) cout << arr[i] << " " ; rotate(arr, n, k); cout << "\nRotated array is\n" ; for (i = 0; i < n; i++) cout << arr[i] << " " ; return 0; } |
Java
// Java program to cyclically rotate an array by one import java.util.*; class Main { public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 4 , 5 }; int n = arr.length; int k = 1 ; // No. of rotations int i, j; System.out.println( "Given array is " ); for (i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); // Reverse the first n-1 terms for (i = 0 , j = n - k - 1 ; i < j; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Reverse the entire array for (i = 0 , j = n - 1 ; i < j; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } System.out.println( "\nRotated array is" ); for (i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } } |
Python3
arr = [ 1 , 2 , 3 , 4 , 5 ] n = len (arr) k = 1 # No. of rotations i, j = 0 , 0 print ( "Given array is" ) for i in range (n): print (arr[i], end = " " ) # Reverse the first n-1 terms for i, j in zip ( range ( 0 , (n - k) / / 2 ), range (n - k - 1 , (n - k) / / 2 - 1 , - 1 )): temp = arr[i] arr[i] = arr[j] arr[j] = temp # Reverse the entire array for i, j in zip ( range ( 0 , n / / 2 ), range (n - 1 , n / / 2 - 1 , - 1 )): temp = arr[i] arr[i] = arr[j] arr[j] = temp print ( "\nRotated array is" ) for i in range (n): print (arr[i], end = " " ) |
C#
using System; class Program { static void Main( string [] args) { int [] arr = { 1, 2, 3, 4, 5 }; int n = arr.Length; int k = 1; // No. of rotations int i, j; Console.WriteLine( "Given array is:" ); for (i = 0; i < n; i++) Console.Write(arr[i] + " " ); // Reverse the first n-1 terms for (i = 0, j = n - k - 1; i < j; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Reverse the entire array for (i = 0, j = n - 1; i < j; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } Console.WriteLine( "\nRotated array is:" ); for (i = 0; i < n; i++) Console.Write(arr[i] + " " ); Console.ReadLine(); } } // This code is contributed by Prajwal Kandekar |
Javascript
let arr = [1, 2, 3, 4, 5]; let n = arr.length; let k = 1; // No. of rotations let i, j; console.log( "Given array is" ); for (i = 0; i < n; i++) { process.stdout.write(arr[i] + " " ); } // Reverse the first n-1 terms for (i = 0, j = n - k - 1; i < j; i++, j--) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Reverse the entire array for (i = 0, j = n - 1; i < j; i++, j--) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } console.log( "\nRotated array is" ); console.log(); for (i = 0; i < n; i++) { process.stdout.write(arr[i] + " " ); } |
Given array is 1 2 3 4 5 Rotated array is 5 1 2 3 4
Time Complexity: O(n), as we are reversing the array. Where n is the number of elements in the array.
Auxiliary Space: O(1), as we are using constant space.
Contact Us