You are given an array. Rotate the array clockwise.
Examples:
Input: arr[] = {1, 7, 3, 4, 5}
Output: arr[] = {5, 1, 7, 3, 4}j
Approach 1: Cyclic Method
In this approach, we will rotate the array in-place i.e., we will be rotating the array without using any extra space.
Algorithm
- Iterate over the input array and store the last element of the input array in a separate variable, let’s say, temp.
- Shift the remaining elements one position ahead of their previous positions.
- Swap the temp variable with the first element of the input array.
- Return the array.
The? ?implementation? ?of? ?the? ?above-discussed? ?approach? ?is:? ?
C++ Programming
# include <iostream>
using namespace std;
// function to rotate
// given array by a factor of 1
void rotateArray(int arr[], int n)
{
int x = arr[n - 1], i;
for (i = n - 1; i > 0; i--)
arr[i] = arr[i - 1];
arr[0] = x;
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7}, i;
int n = sizeof(arr) /
sizeof(arr[0]);
rotateArray(arr, n);
for (i = 0; i < n; i++)
cout << arr[i] << " ";
cout << "\n\n";
return 0;
}
Output
7 1 2 3 4 5 6
Java Programming
import java.util.Arrays;
public class Test
{
static int arr[] = new int[]{1, 2, 3, 4, 5, 6, 7};
// method to rotate
// given array by a factor of 1
static void rotateArray()
{
int x = arr[arr.length-1], i;
for (i = arr.length-1; i > 0; i--)
arr[i] = arr[i-1];
arr[0] = x;
}
public static void main(String[] args)
{
rotateArray();
System.out.println(Arrays.toString(arr));
System.out.print("\n");
}
}
Output
[7, 1, 2, 3, 4, 5, 6]
Python Programming
# function to rotate
# given array by a factor of 1
def rotateArray(arr, n):
x = arr[n - 1]
for i in range(n - 1, 0, -1):
arr[i] = arr[i - 1];
arr[0] = x;
# Driver function
arr= [1, 2, 3, 4, 5, 6, 7]
n = len(arr)
rotateArray(arr, n)
for i in range(0, n):
print (arr[i], end = ' ')
Output
7 1 2 3 4 5 6
C# Programming
using System;
public class Test
{
static int []arr = new int[]{1, 2, 3, 4, 5, 6, 7};
// function to rotate
// given array by a factor of 1
static void rotateArray()
{
int x = arr[arr.Length - 1], i;
for (i = arr.Length - 1; i > 0; i--)
arr[i] = arr[i-1];
arr[0] = x;
}
// Driver Code
public static void Main()
{
rotateArray();
string Rotated_array = string.Join(" ", arr);
Console.WriteLine(Rotated_array);
Console.Write("\n");
}
}
Output
7 1 2 3 4 5 6
Complexity Analysis
Time Complexity : O(n) where n is the number of elements of the array as we are simply linearly iterating over the array.
Approach 2: Block Swap
This method is called the Block Swap method because we are rotating the array by dividing the array into subarray blocks.
Algorithm
- Initialize two arrays, let’s say A and B.
- Choose an element let’s say d and insert elements from 0-d-1 in array A and elements from d-n-1 in array B.
- Check for the shorter array and divide the longer one in two parts, such that one of the parts is equal to the shorter array.
- Swap them.
- When A and B are of the same size, swap them.
The? ?implementation? ?of? ?the? ?above-discussed? ?approach? ?is:? ?
C++ Programming
#include <bits/stdc++.h>
using namespace std;
// prototypes of the functions
// to be used.
void printRotatedArray(int arr[], int size);
void swap(int arr[], int fi, int si, int d);
// function to rotate the array passed as a
// parameter to it
void rotateArray(int arr[], int d, int n)
{
// if d is 0 or
// if d is equal to n, then
// return
if(d == 0 || d == n)
return;
// case, where d is
// equal to n /2.
if(n - d == d)
{
swap(arr, 0, n - d, d);
return;
}
// if the subarray A = arr[0..d-1]
// is smaller
if(d < n - d)
{
swap(arr, 0, n - d, d);
rotateArray(arr, d, n - d);
}
// if the subarray B = arr[d..n-1]
// is smaller
else
{
swap(arr, 0, d, n - d);
rotateArray(arr + n - d, 2 * d - n, d);
}
}
// function to print the
// rotated array.
void printRotatedArray(int arr[], int size)
{
int i;
for(i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// function to swap d elements
// starting with fi and si.
void swap(int arr[], int fi, int si, int d)
{
int i, temp;
for(i = 0; i < d; i++)
{
temp = arr[fi + i];
arr[fi + i] = arr[si + i];
arr[si + i] = temp;
}
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7};
rotateArray(arr, 2, 7);
printRotatedArray(arr, 7);
cout << "\n\n";
return 0;
}
Output
3 4 5 6 7 1 2
Java Programming
import java.util.*;
class Main
{
public static void rotateArray(int arr[], int d,
int n)
{
rotateArrayRec(arr, 0, d, n);
}
// function to rotate the array passed as a
// parameter to it
public static void rotateArrayRec(int arr[], int i,int d, int n)
{
// if d is 0 or
// if d is equal to n, then
// return
if(d == 0 || d == n)
return;
// case, where d is
// equal to n /2.
if(n - d == d)
{
swap(arr, i, n - d + i, d);
return;
}
// if the subarray A = arr[0..d-1]
// is smaller
if(d < n - d)
{
swap(arr, i, n - d + i, d);
rotateArrayRec(arr, i, d, n - d);
}
// if the subarray B = arr[d..n-1]
// is smaller
else
{
swap(arr, i, d, n - d);
rotateArrayRec(arr, n - d + i, 2 * d - n, d);
}
}
// function to print the
// rotated array.
public static void printRotatedArray(int arr[], int size)
{
int i;
for(i = 0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
// function to swap d elements
// starting with fi and si.
public static void swap(int arr[], int fi, int si, int d)
{
int i, temp;
for(i = 0; i < d; i++)
{
temp = arr[fi + i];
arr[fi + i] = arr[si + i];
arr[si + i] = temp;
}
}
public static void main (String[] args)
{
int arr[] = {1, 2, 3, 4, 5, 6, 7};
rotateArray(arr, 2, 7);
printRotatedArray(arr, 7);
System.out.print("\n");
}
}
Output
3 4 5 6 7 1 2
Python Programming
def rotateArray(arr, d, n):
rotateArrayRec(arr, 0, d, n);
# function to rotate the array passed as a
# parameter to it
def rotateArrayRec(arr, i, d, n):
# if d is 0 or
# if d is equal to n, then
# return
if (d == 0 or d == n):
return;
# case, where d is
# equal to n /2.
if (n - d == d):
swap(arr, i, n - d + i, d);
return;
# if the subarray A = arr[0..d-1]
# is smaller
if (d < n - d):
swap(arr, i, n - d + i, d);
rotateArrayRec(arr, i, d, n - d);
# if the subarray B = arr[d..n-1]
# is smaller
else:
swap(arr, i, d, n - d);
rotateArrayRec(arr, n - d + i, 2 * d - n, d);
# function to print the
# rotated array.
def printRotatedArray(arr, size):
for i in range(size):
print(arr[i], end = " ");
print();
# function to swap d elements
# starting with fi and si.
def swap(arr, fi, si, d):
for i in range(d):
temp = arr[fi + i];
arr[fi + i] = arr[si + i];
arr[si + i] = temp;
# Driver Code
if __name__ == '__main__':
arr = [1, 2, 3, 4, 5, 6, 7];
rotateArray(arr, 2, 7);
printRotatedArray(arr, 7);
print();
Output
3 4 5 6 7 1 2
C# Programming
using System;
class Test{
public static void rotateArray(int []arr,int d, int n)
{
rotateArrayRec(arr, 0, d, n);
}
// function to rotate the array passed as a
// parameter to it
public static void rotateArrayRec(int []arr, int i,int d, int n)
{
// if d is 0 or
// if d is equal to n, then
// return
if(d == 0 || d == n)
return;
// case, where d is
// equal to n /2.
if(n - d == d)
{
swap(arr, i, n - d + i, d);
return;
}
// if the subarray A = arr[0..d-1]
// is smaller
if(d < n - d)
{
swap(arr, i, n - d + i, d);
rotateArrayRec(arr, i, d, n - d);
}
// if the subarray B = arr[d..n-1]
// is smaller
else
{
swap(arr, i, d, n - d);
rotateArrayRec(arr, n - d + i,
2 * d - n, d);
}
}
// function to print the
// rotated array.
public static void printRotatedArray(int []arr,int size)
{
int i;
for(i = 0; i < size; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// function to swap the elements
// starting with fi and si.
public static void swap(int []arr, int fi,
int si, int d)
{
int i, temp;
for(i = 0; i < d; i++)
{
temp = arr[fi + i];
arr[fi + i] = arr[si + i];
arr[si + i] = temp;
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4, 5, 6, 7 };
rotateArray(arr, 2, 7);
printRotatedArray(arr, 7);
Console.Write("\n");
}
}
Output
3 4 5 6 7 1 2
Complexity Analysis
Time Complexity : O(n) where n is the number of elements of the array.
Approach 3: Reversal Algorithm
This method solves this problem in O(n) time. As the name suggests, we are breaking the input array into sub-parts and applying reverse operation on both parts to get desired output.
Algorithm
- Create two parts of the input array, let’s say A and B.
- Choose an element let’s say d and insert elements from 0-d-1 in array A and elements from d-n-1 in array B.
- Reverse both A and B.
- Combine them and again reverse them to get the rotated array of the input array.
The? ?implementation? ?of? ?the? ?above-discussed? ?approach? ?is:? ?
C++ Programming
#include <bits/stdc++.h>
using namespace std;
// function to reverse given array
// passed as a parameter
void reverseArray(int arr[], int start, int end)
{
while (start < end)
{ int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp; start++; end--;
}
}
// function to rotate array
// by given the factor d
void rotateArray(int arr[], int d, int n)
{
if (d == 0) return;
// if d is > n
d = d % n;
reverseArray(arr, 0, d - 1);
reverseArray(arr, d, n - 1);
reverseArray(arr, 0, n - 1);
}
// function to print the
// rotated array.
void printRotatedArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int d = 2;
rotateArray(arr, d, n);
printRotatedArray(arr, n);
cout << "\n\n";
return 0;
}
Output
3 4 5 6 7 1 2
Java Programming
import java.io.*;
class Main {
// function to rotate array
// by given the factor d
static void rotateArray(int arr[], int d)
{
if (d == 0)
return;
int n = arr.length;
// if d is > n
d = d % n;
reverseArray(arr, 0, d - 1);
reverseArray(arr, d, n - 1);
reverseArray(arr, 0, n - 1);
}
// function to reverse given array
// passed as a parameter
static void reverseArray(int arr[], int start, int end)
{
int temp;
while (start < end) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
// function to print the
// rotated array.
static void printRotatedArray(int arr[])
{
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = arr.length;
int d = 2;
rotateArray(arr, d);
printRotatedArray(arr);
System.out.print("\n\n");
}
}
Output
3 4 5 6 7 1 2
Python Programming
# function to reverse given array
# passed as a parameter
def reverseArray(arr, start, end):
while (start < end):
temp = arr[start]
arr[start] = arr[end]
arr[end] = temp
start += 1
end = end-1
# function to rotate array
# by given the factor d
def rotateArray(arr, d):
if d == 0:
return
n = len(arr)
# if d is > n
d = d % n
reverseArray(arr, 0, d-1)
reverseArray(arr, d, n-1)
reverseArray(arr, 0, n-1)
# function to print the
# rotated array.
def printRotatedArray(arr):
for i in range(0, len(arr)):
print(arr[i], end=" ")
arr = [1, 2, 3, 4, 5, 6, 7]
n = len(arr)
d = 2
rotateArray(arr, d)
printRotatedArray(arr)
print("\n")
Output
3 4 5 6 7 1 2
C# Programming
using System;
class Test {
// function to rotate array
// by given the factor d
static void rotateArray(int[] arr, int d)
{
if (d == 0)
return;
int n = arr.Length;
// function to rotate array
// by given the factor d
d = d % n;
reverseArray(arr, 0, d - 1);
reverseArray(arr, d, n - 1);
reverseArray(arr, 0, n - 1);
}
// function to reverse given array
// passed as a parameter
static void reverseArray(int[] arr, int start,
int end)
{
int temp;
while (start < end) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
// function to print the
// rotated array.
static void printRotatedArray(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
Console.Write(arr[i] + " ");
}
public static void Main()
{
int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
int n = arr.Length;
int d = 2;
rotateArray(arr, d);
printRotatedArray(arr);
Console.Write("\n");
}
}
Output
3 4 5 6 7 1 2
Complexity Analysis
Time Complexity : O(n) where n is the number of elements of the array.
Approach 4: Juggling Algorithm
In this method, we will juggle between the subsets created by breaking the input array. A number of sets will be the GCD of n and d(a number less than n).
Algorithm
- Divide the input array into subsets containing elements equal to d.
- The number of subsets will be equal to the GCD of n and d.
- Now, rotate the elements within the sets one by one and then combine all the sets.
- Return the final array.
The? ?implementation? ?of? ?the? ?above-discussed? ?approach? ?is:? ?
C++ Programming
#include <bits/stdc++.h>
using namespace std;
// function to find
// gcd of two numbers
int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
// function to rotate the array passed as a
// parameter to it
void rotateArray(int arr[], int d, int n)
{
// case when d >= n
d = d % n;
int g_c_d = gcd(d, n);
for (int i = 0; i < g_c_d; i++) { // to move the ith element int temp = arr[i]; int j = i; while (1) { int k = j + d; if (k >= n)
k = k - n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}
// function to print the rotated array
void printRotatedArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
rotateArray(arr, 2, n);
printRotatedArray(arr, n);
cout << "\n";
return 0;
}
Output
3 4 5 6 7 1 2
JAVA Programming
class RotateArray {
// function to rotate the array passed as a
// parameter to it
void rotateArray(int arr[], int d, int n)
{
// case when d >= n
d = d % n;
int i, j, k, temp;
int g_c_d = gcd(d, n);
for (i = 0; i < g_c_d; i++) { // to move the ith element temp = arr[i]; j = i; while (true) { k = j + d; if (k >= n)
k = k - n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}
// function to print the rotated array
void printRotatedArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
System.out.print(arr[i] + " ");
}
// function to find
// gcd of two numbers
int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
public static void main(String[] args)
{
RotateArray rotate = new RotateArray();
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
rotate.rotateArray(arr, 2, 7);
rotate.printRotatedArray(arr, 7);
System.out.print("\n\n");
}
}
Output
3 4 5 6 7 1 2
Python Programming
# function to rotate the array passed as a
# parameter to it
def rotateArray(arr, d, n):
d = d % n
g_c_d = gcd(d, n)
for i in range(g_c_d):
# to move the ith element
temp = arr[i]
j = i
while 1:
k = j + d
if k >= n:
k = k - n
if k == i:
break
arr[j] = arr[k]
j = k
arr[j] = temp
# function to print the rotated array
def printRotatedArray(arr, size):
for i in range(size):
print ("% d" % arr[i], end ="")
# function to find
# gcd of two numbers
def gcd(a, b):
if b == 0:
return a;
else:
return gcd(b, a % b)
# Driver program to test above functions
arr = [1, 2, 3, 4, 5, 6, 7]
n = len(arr)
d = 2
rotateArray(arr, d, n)
printRotatedArray(arr, n)
print("\n")
Output
3 4 5 6 7 1 2
C# Programming
using System;
class Test {
// function to rotate the array passed as a
// parameter to it
static void rotateArray(int[] arr, int d,
int n)
{
int i, j, k, temp;
// case when d >= n
d = d % n;
int g_c_d = gcd(d, n);
for (i = 0; i < g_c_d; i++) { // to move the ith element temp = arr[i]; j = i; while (true) { k = j + d; if (k >= n)
k = k - n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}
// function to print the rotated array
static void printRotatedArray(int[] arr, int size)
{
for (int i = 0; i < size; i++)
Console.Write(arr[i] + " ");
}
// function to find
// gcd of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
public static void Main()
{
int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
rotateArray(arr, 2, 7);
printRotatedArray(arr, 7);
Console.Write("\n");
}
}
Output
3 4 5 6 7 1 2
Complexity Analysis
Time Complexity : O(n) where n is the number of elements of the array.
Wrapping Up!
In this article, we have learned an amazing as well as easy concept. Rotation of an array is one of the most important data structures and is usually asked in the top interview questions as well. In this article, we have included proper examples with detailed explanations for a better understanding for you. We also learned about how we should think for a solution and then make optimizations in our code in such kinds of problems.
We also discussed four well-explained approaches along with some suitable examples to solve this problem. We also covered in detail how all four of the approaches work and what is the significance of them.
We discussed their time complexity along with a proper explanation. Different programmers prefer different languages for coding. So, we made sure that all our readers can refer to this article.
That’s why this article also contains well-explained codes for all the approaches in the three most popular languages along with their respective outputs attached to the article for a better understanding of a wide range of our readers. We sincerely hope that this article has walked you through some deep and important concepts and how we should approach such kinds of problems. We surely wish you to keep up your practice and crack all the questions easily. With this, we are wrapping up this article.
Happy Learning!
People are also reading:
- Print all subarrays with 0 sum
- Print a given matrix in spiral form
- Maximum of all Subarrays of size K
- Construct a Binary Tree from Inorder and Preorder traversals
- Write a Program to convert given inches into equivalent yard, and feet
- Longest Palindromic Subsequence using Dynamic Programming
- Rearrange an array such that arr[i] = i
- Majority Element
- Minimum Edit Distance
- The Stock Span Problem
Leave a Comment on this Post