Method to Print array after it is right rotated K times
#include <iostream>
#include <vector>
using namespace std;
// Function to calculate the greatest common divisor (GCD) using Euclid's algorithm
int gcd(int a, int b) {
// Keep dividing until b becomes 0
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
// 'a' holds the GCD
return a;
}
// Function to rotate the array 'nums' by 'k' positions to the right
vector<int> rotate_array(vector<int>& nums, int k) {
int n = nums.size();
k = k % n; // Handle cases where k is larger than the length of the array
if (k == 0) {
return nums; // If k is 0, no rotation needed
}
// Calculate the number of cycles based on the GCD of 'n' and 'k'
int cycles = gcd(n, k);
// Perform rotation for each cycle
for (int i = 0; i < cycles; ++i) {
int start = i; // Start index of the current cycle
int current = start; // Current index being processed
int prev = nums[start]; // Store the value to be replaced
while (true) {
// Calculate the next index after rotation
int next_idx = (current + k) % n;
// Swap the values and update 'prev' with the replaced value
int temp = nums[next_idx];
nums[next_idx] = prev;
prev = temp;
// Update 'current' to the next index
current = next_idx;
// Break if the cycle completes (back to the start index)
if (current == start) {
break;
}
}
}
return nums; // Return the rotated array
}
// Driver code
int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6};
int k = 4;
// Rotate the array 'nums' by 'k' positions
vector<int> rotated_nums = rotate_array(nums, k);
// Print the rotated array
for (int num : rotated_nums) {
cout << num << " ";
}
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class Main {
// Function to calculate the greatest common divisor (GCD) using Euclid's algorithm
static int gcd(int a, int b) {
// Keep dividing until b becomes 0
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
// 'a' holds the GCD
return a;
}
// Function to rotate the array 'nums' by 'k' positions to the right
static List<Integer> rotateArray(List<Integer> nums, int k) {
int n = nums.size();
k = k % n; // Handle cases where k is larger than the length of the array
if (k == 0) {
return nums; // If k is 0, no rotation needed
}
// Calculate the number of cycles based on the GCD of 'n' and 'k'
int cycles = gcd(n, k);
// Perform rotation for each cycle
for (int i = 0; i < cycles; ++i) {
int start = i; // Start index of the current cycle
int current = start; // Current index being processed
int prev = nums.get(start); // Store the value to be replaced
while (true) {
// Calculate the next index after rotation
int nextIdx = (current + k) % n;
// Swap the values and update 'prev' with the replaced value
int temp = nums.get(nextIdx);
nums.set(nextIdx, prev);
prev = temp;
// Update 'current' to the next index
current = nextIdx;
// Break if the cycle completes (back to the start index)
if (current == start) {
break;
}
}
}
return nums; // Return the rotated array
}
// Driver code
public static void main(String[] args) {
List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
int k = 4;
// Rotate the array 'nums' by 'k' positions
List<Integer> rotatedNums = rotateArray(nums, k);
// Print the rotated array
for (int num : rotatedNums) {
System.out.print(num + " ");
}
}
}
// This code is contributed by shivamgupta0987654321
import math
def rotate_array(nums, k):
n = len(nums)
k = k % n # handle cases where k is larger than the length of the array
if k == 0:
return nums
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
cycles = gcd(n, k)
for i in range(cycles):
start = i
current = start
prev = nums[start]
while True:
next_idx = (current + k) % n
nums[next_idx], prev = prev, nums[next_idx]
current = next_idx
if current == start:
break
return nums
# Example usage:
nums = [1, 2, 3, 4, 5, 6]
k = 4
rotated_nums = rotate_array(nums, k)
print(rotated_nums)
// Function to calculate the greatest common divisor (GCD) using Euclid's algorithm
function gcd(a, b) {
// Keep dividing until b becomes 0
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
// 'a' holds the GCD
return a;
}
// Function to rotate the array 'nums' by 'k' positions to the right
function rotateArray(nums, k) {
const n = nums.length;
k = k % n; // Handle cases where k is larger than the length of the array
if (k === 0) {
return nums; // If k is 0, no rotation needed
}
// Calculate the number of cycles based on the GCD of 'n' and 'k'
const cycles = gcd(n, k);
// Perform rotation for each cycle
for (let i = 0; i < cycles; ++i) {
let start = i; // Start index of the current cycle
let current = start; // Current index being processed
let prev = nums[start]; // Store the value to be replaced
while (true) {
// Calculate the next index after rotation
let nextIdx = (current + k) % n;
// Swap the values and update 'prev' with the replaced value
let temp = nums[nextIdx];
nums[nextIdx] = prev;
prev = temp;
// Update 'current' to the next index
current = nextIdx;
// Break if the cycle completes (back to the start index)
if (current === start) {
break;
}
}
}
return nums; // Return the rotated array
}
// Driver code
let nums = [1, 2, 3, 4, 5, 6];
let k = 4;
// Rotate the array 'nums' by 'k' positions
let rotatedNums = rotateArray(nums, k);
// Print the rotated array
console.log(rotatedNums.join(" "));
Output
[3, 4, 5, 6, 1, 2]
Time Complexity: O(N). Auxiliary Space: O(1).
Please see following posts for other methods of array rotation: https://www.w3wiki.org/print-array-after-it-is-right-rotated-k-times-set-2/
Print array after it is right rotated K times
Given an Array of size N and a value K, around which we need to right rotate the array. How do you 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
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach:
- We will first take the mod of K by N (K = K % N) because, after every N rotation, the 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 the rightmost Kth element (a[N + i -K]).
- Otherwise, Print the array after ‘K’ elements (a[i – K]).
Below is the implementation of the above approach.
// C++ implementation of right rotation
// of an array K number of times
#include<bits/stdc++.h>
using namespace std;
// Function to rightRotate array
void RightRotate(int a[], int n, int k)
{
// If rotation is greater
// than size of array
k = k % n;
for(int i = 0; i < n; i++)
{
if(i < k)
{
// Printing rightmost
// kth elements
cout << a[n + i - k] << " ";
}
else
{
// Prints array after
// 'k' elements
cout << (a[i - k]) << " ";
}
}
cout << "\n";
}
// Driver code
int main()
{
int Array[] = { 1, 2, 3, 4, 5 };
int N = sizeof(Array) / sizeof(Array[0]);
int K = 2;
RightRotate(Array, N, K);
}
// This code is contributed by Surendra_Gangwar
// Java Implementation of Right Rotation
// of an Array K number of times
import java.util.*;
import java.lang.*;
import java.io.*;
class Array_Rotation
{
// Function to rightRotate array
static void RightRotate(int a[],
int n, int k)
{
// If rotation is greater
// than size of array
k=k%n;
for(int i = 0; i < n; i++)
{
if(i<k)
{
// Printing rightmost
// kth elements
System.out.print(a[n + i - k]
+ " ");
}
else
{
// Prints array after
// 'k' elements
System.out.print(a[i - k]
+ " ");
}
}
System.out.println();
}
// Driver program
public static void main(String args[])
{
int Array[] = {1, 2, 3, 4, 5};
int N = Array.length;
int K = 2;
RightRotate(Array, N, K);
}
}
// This code is contributed by M Vamshi Krishna
# Python3 implementation of right rotation
# of an array K number of times
# Function to rightRotate array
def RightRotate(a, n, k):
# If rotation is greater
# than size of array
k = k % n;
for i in range(0, n):
if(i < k):
# Printing rightmost
# kth elements
print(a[n + i - k], end = " ");
else:
# Prints array after
# 'k' elements
print(a[i - k], end = " ");
print("\n");
# Driver code
Array = [ 1, 2, 3, 4, 5 ];
N = len(Array);
K = 2;
RightRotate(Array, N, K);
# This code is contributed by Code_Mech
// C# implementation of right rotation
// of an array K number of times
using System;
class GFG{
// Function to rightRotate array
static void RightRotate(int []a,
int n, int k)
{
// If rotation is greater
// than size of array
k = k % n;
for(int i = 0; i < n; i++)
{
if(i < k)
{
// Printing rightmost
// kth elements
Console.Write(a[n + i - k] + " ");
}
else
{
// Prints array after
// 'k' elements
Console.Write(a[i - k] + " ");
}
}
Console.WriteLine();
}
// Driver code
public static void Main(String []args)
{
int []Array = { 1, 2, 3, 4, 5 };
int N = Array.Length;
int K = 2;
RightRotate(Array, N, K);
}
}
// This code is contributed by Rohit_ranjan
// Function to right rotate array
function rightRotate(arr, k) {
const n = arr.length;
// If rotation is greater than size of array
k = k % n;
for (let i = 0; i < n; i++) {
if (i < k) {
// Printing rightmost kth elements
process.stdout.write(arr[n + i - k] + " ");
} else {
// Prints array after 'k' elements
process.stdout.write(arr[i - k] + " ");
}
}
process.stdout.write("\n");
}
// Driver code
const Array = [1, 2, 3, 4, 5];
const K = 2;
rightRotate(Array, K);
Output
4 5 1 2 3
Time complexity : O(n)
Auxiliary Space : O(1)