Print array after it is right rotated K times using Recursion
Step-by-step approach:
- If “k” = 0, return the array “arr” and terminate the recursion.
- Else, move the last element to the first position and rotate the array “arr” to the right by one position by moving each element one position to the right.
- Recursively call the “rotateArray()” function with the same array “arr”, of size “n”, and k-1.
- Return the rotated array “arr” and terminate the recursion.
Below is the implementation of the above Recursive approach:
#include <iostream>
using namespace std;
// Function to rotate the array
void rotateArray(int arr[], int n, int k) {
if (k == 0) {
return;
}
// Rotate the array to the right by one position
int temp = arr[n - 1];
for (int i = n - 1; i > 0; i--) {
arr[i] = arr[i - 1];
}
arr[0] = temp;
// Recursively rotate the remaining elements k-1 times
rotateArray(arr, n, k - 1);
}
// Driver code
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;
}
#include <stdio.h>
// Function to rotate the array
void rotateArray(int arr[], int n, int k) {
if (k == 0) {
return;
}
// Rotate the array to the right by one position
int temp = arr[n-1];
for (int i = n-1; i > 0; i--) {
arr[i] = arr[i-1];
}
arr[0] = temp;
// Recursively rotate the remaining elements k-1 times
rotateArray(arr, n, k-1);
}
// Driver code
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;
}
import java.util.*;
public class Main {
// Function to rotate the array
public static void rotateArray(int[] arr, int n, int k) {
if (k == 0) {
return;
}
// Rotate the array to the right by one position
int temp = arr[n-1];
for (int i = n-1; i > 0; i--) {
arr[i] = arr[i-1];
}
arr[0] = temp;
// Recursively rotate the remaining elements k-1 times
rotateArray(arr, n, k-1);
}
// Driver code
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();
}
}
from __future__ import print_function
def GFG(arr, n, k):
if k == 0:
return
# Rotate the array to the right by one position
temp = arr[n-1]
for i in range(n-1, 0, -1):
arr[i] = arr[i-1]
arr[0] = temp
# Recursively rotate the remaining elements k-1 times
GFG(arr, n, k-1)
# Driver code
if __name__ == "__main__":
arr = [1, 3, 5, 7, 9]
n = len(arr)
k = 2
GFG(arr, n, k)
for i in range(n):
print(arr[i], end=" ")
print()
using System;
public class GFG {
// Function to rotate the array
public static void rotateArray(int[] arr, int n, int k) {
if (k == 0) {
return;
}
// Rotate the array to the right by one position
int temp = arr[n-1];
for (int i = n-1; i > 0; i--) {
arr[i] = arr[i-1];
}
arr[0] = temp;
// Recursively rotate the remaining elements k-1 times
rotateArray(arr, n, k-1);
}
// Driver code
public static void Main() {
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++) {
Console.Write(arr[i] + " ");
}
Console.WriteLine();
}
}
function rotateArray(arr, n, k) {
if (k === 0) {
return;
}
// Rotate the array to the right by one position
const temp = arr[n - 1];
for (let i = n - 1; i > 0; i--) {
arr[i] = arr[i - 1];
}
arr[0] = temp;
// Recursively rotate the remaining elements k-1 times
rotateArray(arr, n, k - 1);
}
// Driver code
const arr = [1, 3, 5, 7, 9];
const n = arr.length;
const k = 2;
rotateArray(arr, n, k);
console.log(arr); // Output: [7, 9, 1, 3, 5]
// This code is contributed by Vaibhav Saroj
Output
7 9 1 3 5
Time Complexity: O(k*n)
Auxiliary Space: O(k)
Print array after it is right rotated K times using Cyclic Rotation
In this approach, we perform a cyclic rotation of the array elements to right by the K positions. We use the modulo operator (%) to the handle cases where K may be greater than the size of the array. This approach ensures that we rotate the array effectively without any unnecessary iterations.
Algorithm:
- Calculate the effective rotation count by the taking the modulo of the K with the size of the array (n).
- Iterate through each element of the array.
- Print the element at index (n + i – K) % n where i is the current index.
- By using this formula we ensure that we access the correct element after rotation.
Below is the implementation of above approach:
#include <iostream>
#include <vector>
using namespace std;
void GFG(int Array[], int N, int K) {
// Calculate the effective rotation count
int effectiveRotation = K % N;
// Iterate through each element of the array
for (int i = 0; i < N; i++) {
// Print the element at the rotated index
cout << Array[(N + i - effectiveRotation) % N] << " ";
}
cout << endl;
}
// Main function
int main() {
// Initialize the array
int Array[] = {1, 2, 3, 4, 5};
int N = sizeof(Array) / sizeof(Array[0]);
int K = 2;
// Call the function to perform cyclic rotation and
// print the output
GFG(Array, N, K);
return 0;
}
import java.util.Arrays;
public class Solution {
// Function to perform cyclic rotation of an array
public static void GFG(int[] array, int N, int K) {
// Calculate the effective rotation count
int effectiveRotation = K % N;
// Iterate through each element of the array
for (int i = 0; i < N; i++) {
// Print the element at the rotated index
System.out.print(array[(N + i - effectiveRotation) % N] + " ");
}
System.out.println();
}
// Main function
public static void main(String[] args) {
// Initialize the array
int[] array = {1, 2, 3, 4, 5};
int N = array.length;
int K = 2;
// Call the function to perform cyclic rotation and
// print the output
GFG(array, N, K);
}
}
// This code is contributed by Akshita
def cyclic_rotation(array, K):
N = len(array)
effective_rotation = K % N
rotated_array = [(array[(N + i - effective_rotation) % N]) for i in range(N)]
return rotated_array
# Main function
if __name__ == "__main__":
# Initialize the array
array = [1, 2, 3, 4, 5]
K = 2
# Call the function to perform cyclic rotation
rotated_array = cyclic_rotation(array, K)
# Print the output
print(rotated_array)
# This code is contributed by Shivam Gupta
function GFG(Array, N, K) {
// Calculate the effective rotation count
const effectiveRotation = K % N;
// Iterate through each element of the array
for (let i = 0; i < N; i++) {
// Print the element at the rotated index
console.log(Array[(N + i - effectiveRotation) % N] + " ");
}
console.log(); // Print a newline
}
// Main function
function main() {
// Initialize the array
const Array = [1, 2, 3, 4, 5];
const N = Array.length;
const K = 2;
// Call the function to perform cyclic rotation and
// print the output
GFG(Array, N, K);
}
// Call the main function to execute the example usage
main();
output :
4 5 1 2 3
Time Complexity: O(N)
Auxiliary Space: O(1)
Print array after it is right rotated K times | Set 2
Given an array arr[] of size N and a value K, the task is to print the array rotated by K times to the right.
Examples:
Input: arr = {1, 3, 5, 7, 9}, K = 2
Output: 7 9 1 3 5Input: arr = {1, 2, 3, 4, 5}, K = 4
Output: 2 3 4 5 1
Algorithm: The given problem can be solved by reversing subarrays. Below steps can be followed to solve the problem:
- Reverse all the array elements from 1 to N -1
- Reverse the array elements from 1 to K – 1
- Reverse the array elements from K to N -1
#include <bits/stdc++.h>
using namespace std;
// Function to rotate the array
// to the right, K times
void RightRotate(int Array[], int N, int K) {
// Normalize K to avoid unnecessary full rotations
K = K % N;
// Reverse all the array elements
reverse(Array, Array + N);
// Reverse the first K elements
reverse(Array, Array + K);
// Reverse the elements from K to the end of the array
reverse(Array + K, Array + N);
// Print the array after rotation
for (int i = 0; i < N; i++) {
cout << Array[i] << " ";
}
cout << endl;
}
// Driver code
int main() {
// Initialize the array
int Array[] = { 1, 2, 3, 4, 5 };
// Find the size of the array
int N = sizeof(Array) / sizeof(Array[0]);
// Initialize K
int K = 4;
// Call the function and print the answer
RightRotate(Array, N, K);
return 0;
}
import java.util.*;
class GFG {
// Function to rotate the array to the right, K times
static void RightRotate(int[] Array, int N, int K) {
// Normalize K
K = K % N;
// Reverse all the array elements
for (int i = 0; i < N / 2; i++) {
int temp = Array[i];
Array[i] = Array[N - i - 1];
Array[N - i - 1] = temp;
}
// Reverse the first K elements
for (int i = 0; i < K / 2; i++) {
int temp = Array[i];
Array[i] = Array[K - i - 1];
Array[K - i - 1] = temp;
}
// Reverse the elements from K to the end of the array
for (int i = 0; i < (N - K) / 2; i++) {
int temp = Array[i + K];
Array[i + K] = Array[N - i - 1];
Array[N - i - 1] = temp;
}
// Print the array after rotation
for (int i = 0; i < N; i++) {
System.out.print(Array[i] + " ");
}
System.out.println();
}
// Driver code
public static void main(String[] args) {
// Initialize the array
int Array[] = { 1, 2, 3, 4, 5 };
// Find the size of the array
int N = Array.length;
// Initialize K
int K = 4;
// Call the function and print the answer
RightRotate(Array, N, K);
}
}
import math
# Function to rotate the array to the right, K times
def RightRotate(Array, N, K):
# Normalize K
K = K % N
# Reverse all the array elements
for i in range(N // 2):
temp = Array[i]
Array[i] = Array[N - i - 1]
Array[N - i - 1] = temp
# Reverse the first K elements
for i in range(K // 2):
temp = Array[i]
Array[i] = Array[K - i - 1]
Array[K - i - 1] = temp
# Reverse the elements from K to the end of the array
for i in range((N - K) // 2):
temp = Array[i + K]
Array[i + K] = Array[N - i - 1]
Array[N - i - 1] = temp
# Print the array after rotation
for i in range(N):
print(Array[i], end=" ")
print()
# Driver Code
arr = [1, 2, 3, 4, 5]
N = len(arr)
K = 4
# Call the function and print the answer
RightRotate(arr, N, K)
using System;
class GFG {
// Function to rotate the array to the right, K times
static void RightRotate(int[] Array, int N, int K) {
// Normalize K
K = K % N;
// Reverse all the array elements
for (int i = 0; i < N / 2; i++) {
int temp = Array[i];
Array[i] = Array[N - i - 1];
Array[N - i - 1] = temp;
}
// Reverse the first K elements
for (int i = 0; i < K / 2; i++) {
int temp = Array[i];
Array[i] = Array[K - i - 1];
Array[K - i - 1] = temp;
}
// Reverse the elements from K to the end of the array
for (int i = 0; i < (N - K) / 2; i++) {
int temp = Array[i + K];
Array[i + K] = Array[N - i - 1];
Array[N - i - 1] = temp;
}
// Print the array after rotation
for (int i = 0; i < N; i++) {
Console.Write(Array[i] + " ");
}
Console.WriteLine();
}
// Driver code
public static void Main() {
// Initialize the array
int[] Array = { 1, 2, 3, 4, 5 };
// Find the size of the array
int N = Array.Length;
// Initialize K
int K = 4;
// Call the function and print the answer
RightRotate(Array, N, K);
}
}
// Function to rotate the array
// to the right, K times
function RightRotate(Array, N, K)
{
// Reverse all the array elements
for (let i = 0; i < N / 2; i++) {
let temp = Array[i];
Array[i] = Array[N - i - 1];
Array[N - i - 1] = temp;
}
// Reverse the first k elements
for (let i = 0; i < K / 2; i++) {
let temp = Array[i];
Array[i] = Array[K - i - 1];
Array[K - i - 1] = temp;
}
// Reverse the elements from K
// till the end of the array
for (let i = 0; i < (N-K) / 2; i++) {
let temp = Array[(i + K)];
Array[(i + K)] = Array[(N - i - 1)];
Array[(N - i - 1) % N] = temp;
}
// Print the array after rotation
let result = "";
for (let i = 0; i < N; i++) {
result += Array[i] + " ";
}
console.log(result.trim());
}
Output
2 3 4 5 1
Time Complexity: O(N)
Auxiliary Space: O(1)