Program to Rotate an Array

Posted in

Program to Rotate an Array
vinaykhatri

Vinay Khatri
Last updated on April 23, 2024

    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

    1. Iterate over the input array and store the last element of the input array in a separate variable, let’s say, temp.
    2. Shift the remaining elements one position ahead of their previous positions.
    3. Swap the temp variable with the first element of the input array.
    4. 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

    1. Initialize two arrays, let’s say A and B.
    2. 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.
    3. 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.
    4. Swap them.
    5. 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

    1. Create two parts of the input array, let’s say A and B.
    2. 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.
    3. Reverse both A and B.
    4. 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

    1. Divide the input array into subsets containing elements equal to d.
    2. The number of subsets will be equal to the GCD of n and d.
    3. Now, rotate the elements within the sets one by one and then combine all the sets.
    4. 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:

    Leave a Comment on this Post

    0 Comments