Given an Array of size N and a values K, around which we need to right rotate the array. How to quickly print the right rotated array?
Examples :
Input: Array[] = {1, 3, 5, 7, 9}, K = 2.
Output: 7 9 1 3 5
Explanation:
After 1st rotation - {9, 1, 3, 5, 7}
After 2nd rotation - {7, 9, 1, 3, 5}
Input: Array[] = {1, 2, 3, 4, 5}, K = 4.
Output: 2 3 4 5 1
Approach:
- We will first take mod of K by N (K = K % N) because after every N rotation array will become the same as the initial array.
- Now, we will iterate the array from i = 0 to i = N-1 and check,
- If i < K, Print rightmost Kth element (a[N + i -K]).
- Otherwise, Print array after ‘K’ elements (a[i – K]).
Below is the implementation of the above approach.
C++
#include<bits/stdc++.h>
using namespace std;
void RightRotate( int a[], int n, int k)
{
k = k % n;
for ( int i = 0; i < n; i++)
{
if (i < k)
{
cout << a[n + i - k] << " " ;
}
else
{
cout << (a[i - k]) << " " ;
}
}
cout << "\n" ;
}
int main()
{
int Array[] = { 1, 2, 3, 4, 5 };
int N = sizeof (Array) / sizeof (Array[0]);
int K = 2;
RightRotate(Array, N, K);
}
|
Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Array_Rotation
{
static void RightRotate( int a[],
int n, int k)
{
k=k%n;
for ( int i = 0 ; i < n; i++)
{
if (i<k)
{
System.out.print(a[n + i - k]
+ " " );
}
else
{
System.out.print(a[i - k]
+ " " );
}
}
System.out.println();
}
public static void main(String args[])
{
int Array[] = { 1 , 2 , 3 , 4 , 5 };
int N = Array.length;
int K = 2 ;
RightRotate(Array, N, K);
}
}
|
Python3
def RightRotate(a, n, k):
k = k % n;
for i in range ( 0 , n):
if (i < k):
print (a[n + i - k], end = " " );
else :
print (a[i - k], end = " " );
print ( "\n" );
Array = [ 1 , 2 , 3 , 4 , 5 ];
N = len (Array);
K = 2 ;
RightRotate(Array, N, K);
|
C#
using System;
class GFG{
static void RightRotate( int []a,
int n, int k)
{
k = k % n;
for ( int i = 0; i < n; i++)
{
if (i < k)
{
Console.Write(a[n + i - k] + " " );
}
else
{
Console.Write(a[i - k] + " " );
}
}
Console.WriteLine();
}
public static void Main(String []args)
{
int []Array = { 1, 2, 3, 4, 5 };
int N = Array.Length;
int K = 2;
RightRotate(Array, N, K);
}
}
|
Javascript
function RightRotate(a, n, k)
{
k = k % n;
for (let i = 0; i < n; i++) {
if (i < k) {
document.write(a[n + i - k] + " " );
}
else {
document.write((a[i - k]) + " " );
}
}
document.write( "<br>" );
}
let Array = [1, 2, 3, 4, 5];
let N = Array.length;
let K = 2;
RightRotate(Array, N, K);
|
Time complexity : O(n)
Auxiliary Space : O(1)
Method 2: Reversing the array
Approach: The approach is simple yet optimized. The idea is to reverse the array three times. For the first time we reverse only the last k elements. Second time we will reverse first n-k(n=size of array) elements. Finally we will get our rotated array by reversing the entire array.
Code:
C++
#include <iostream>
using namespace std;
int main()
{
int arr[] = { 1, 3, 5, 7, 9, 11 };
int n = sizeof (arr) / sizeof (arr[0]);
int k = 3;
k = k % n;
int i, j;
for (i = n - k, j = n - 1; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for (i = 0, j = n - k - 1; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for (i = 0, j = n - 1; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for ( int i = 0; i < n; i++) {
cout << arr[i] << " " ;
}
return 0;
}
|
C
#include <stdio.h>
int main()
{
int arr[] = { 1, 3, 5, 7, 9, 11 };
int n = sizeof (arr) / sizeof (arr[0]);
int k = 3;
k = k % n;
int i, j;
for (i = n - k, j = n - 1; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for (i = 0, j = n - k - 1; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for (i = 0, j = n - 1; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for ( int i = 0; i < n; i++) {
printf ( "%d " , arr[i]);
}
return 0;
}
|
Java
import java.io.*;
class GFG {
public static void main(String[] args)
{
int arr[] = new int [] { 1 , 3 , 5 , 7 , 9 , 11 };
int n = arr.length;
int k = 3 ;
k = k % n;
int i, j;
for (i = n - k, j = n - 1 ; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for (i = 0 , j = n - k - 1 ; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for (i = 0 , j = n - 1 ; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for ( int t = 0 ; t < n; t++) {
System.out.print(arr[t] + " " );
}
}
}
|
Python3
class GFG :
@staticmethod
def main( args) :
arr = [ 1 , 3 , 5 , 7 , 9 , 11 ]
n = len (arr)
k = 3
k = k % n
i = 0
j = 0
i = n - k
j = n - 1
while (i < j) :
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
i + = 1
j - = 1
i = 0
j = n - k - 1
while (i < j) :
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
i + = 1
j - = 1
i = 0
j = n - 1
while (i < j) :
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
i + = 1
j - = 1
t = 0
while (t < n) :
print ( str (arr[t]) + " " , end = "")
t + = 1
if __name__ = = "__main__" :
GFG.main([])
|
C#
using System;
public class GFG{
public static void Main(String []args)
{
int []arr = { 1, 3, 5, 7, 9, 11 };
int n = arr.Length;
int k = 3;
k = k % n;
int i, j;
for (i = n - k, j = n - 1; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for (i = 0, j = n - k - 1; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for (i = 0, j = n - 1; i < j; i++, j--) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for ( int t = 0; t < n; t++) {
Console.Write(arr[t] + " " );
}
}
}
|
Javascript
let arr = [ 1, 3, 5, 7, 9, 11 ];
let n = arr.length;
let k = 3;
k = k % n;
let i, j;
for (i = n - k, j = n - 1; i < j; i++, j--) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for (i = 0, j = n - k - 1; i < j; i++, j--) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for (i = 0, j = n - 1; i < j; i++, j--) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
for (let i = 0; i < n; i++) {
console.log(arr[i]+ " " );
}
|
Complexity Analysis:
Time Complexity: O(N).
Auxiliary Space: O(1).
Approach 3: Recursive approach
Algorithm :
Here is the step-by-step algorithm .
- “rotateArray” function will take an array “arr” , it’s size is “n” and the number of rotations “k” as an input.
- To reduce the number of rotations, we compute ‘k’ modulo ‘n’ ( k%=n) .
- Using the STL library’s “reverse” function, reverse the first portion of the array from the start up to the “n – k” index.
- Using the “reverse” function from the STL library, reverse the second part of the array from the “n – k” index to the end.
- To get the rotated array, reverse the entire array using the “reverse” function in the STL library.
- Then ,we’ll return the rotated array.
Here is the pseudocode for the above algorithm:
function rotateArray(arr, n, k):
// Reduce the number of rotations
k = k % n
// Reverse the first part of the array
reverse(arr, arr + n – k)
// Reverse the second part of the array
reverse(arr + n – k, arr + n)
// Reverse the entire array
reverse(arr, arr + n)
// Driver code
arr = {1, 3, 5, 7, 9}
n = size(arr)
k = 2
rotateArray(arr, n, k)
for i = 0 to n-1:
print arr[i]
// This is contributed by Vaibhav Saroj
Here is the implementation of pseudocode:
C++
#include <bits/stdc++.h>
using namespace std;
void rotateArray( int arr[], int n, int k) {
k %= n;
reverse(arr, arr + n - k);
reverse(arr + n - k, arr + n);
reverse(arr, arr + n);
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof (arr)/ sizeof (arr[0]);
int k = 2;
rotateArray(arr, n, k);
for ( int i = 0; i < n; i++) {
cout << arr[i] << " " ;
}
cout << endl;
return 0;
}
|
C
#include <stdio.h>
void rotateArray( int arr[], int n, int k) {
if (k == 0) {
return ;
}
int temp = arr[n-1];
for ( int i = n-1; i > 0; i--) {
arr[i] = arr[i-1];
}
arr[0] = temp;
rotateArray(arr, n, k-1);
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof (arr)/ sizeof (arr[0]);
int k = 2;
rotateArray(arr, n, k);
for ( int i = 0; i < n; i++) {
printf ( "%d " , arr[i]);
}
printf ( "\n" );
return 0;
}
|
Java
import java.util.Arrays;
public class GFG {
static void rotateArray( int [] arr, int n, int k) {
k %= n;
reverse(arr, 0 , n - k - 1 );
reverse(arr, n - k, n - 1 );
reverse(arr, 0 , n - 1 );
}
static void reverse( int [] arr, int start, int end) {
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
public static void main(String[] args) {
int [] arr = { 1 , 3 , 5 , 7 , 9 };
int n = arr.length;
int k = 2 ;
rotateArray(arr, n, k);
for ( int i = 0 ; i < n; i++) {
System.out.print(arr[i] + " " );
}
System.out.println();
}
}
|
Python3
def rotate_array(arr, n, k):
k % = n
arr[:n - k] = arr[:n - k][:: - 1 ]
arr[n - k:] = arr[n - k:][:: - 1 ]
arr[:] = arr[:: - 1 ]
arr = [ 1 , 3 , 5 , 7 , 9 ]
n = len (arr)
k = 2
rotate_array(arr, n, k)
for i in range (n):
print (arr[i], end = " " )
print ()
|
Time Complexity: O(N).
Auxiliary Space: O(1).
Please see following posts for other methods of array rotation:
https://www.geeksforgeeks.org/print-array-after-it-is-right-rotated-k-times-set-2/
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!