Circular Right Rotation Of An Array

Circular Right Rotation Of An Array
Circular Right Rotation Of An Array

Introduction

An array is a collection of elements of similar data types. We can have an array of integers or characters or structures etc. In this blog, we are going to learn about the circular right rotation of an array. Now you must be wondering what is meant by right rotation!! The right rotation of an array implies that you have to rotate the array towards the right, i.e., clockwise rotation of an array. This is the most common problem asked by interviewers, so read all the concepts discussed here carefully.

Problem: You are given an array of integers, circularly rotate the array to the right by one.

Let’s understand the problem more clearly with the below example.


Suppose you are given an array arr of integers.

123456

Now you have to rotate the array clockwise by one. So you have to produce output as:-

612345

Now you’re clear with the problem statement so let’s move towards solving it.

Method 1: Using Loops

To rotate the array circularly, we can use loops. Let’s discuss the steps first then we will move towards code.

Step 1:  Store the last element of the array in a variable temp.

Step 2:  All the elements of the array will be shifted by one towards the right.

Step 3:  Replace the first element of the array with the value stored in temp.

Java program for Circular Right Rotation of an Array

import java.util.Arrays;
public class Rotating {
    static int arr[] = new int[] {1,2,3,4,5,6};

    // Function for rotating the array
    static void rotateRight() {
        int temp = arr[arr.length - 1];
        //shifting the array elements by one
        for (int i = arr.length - 1; i > 0; i--)
            arr[i] = arr[i - 1];

        //Replacing the first array element by temp
        arr[0] = temp;
    }


    public static void main(String[] args) {
        System.out.println("Array given in input is:");
        System.out.println(Arrays.toString(arr));

        rotateRight();

        System.out.println("Array after rotation is:");
        System.out.println(Arrays.toString(arr));
    }
}


Output: 
Array given in input is
1 2 3 4 5 6 
Array after rotation is
6 1 2 3 4 5 

C++ program for Circular Right Rotation Of an Array

#include <iostream>
using namespace std;

void rotateRight(int * arr, int n) {
   int temp = arr[n - 1];
   //shifting the array elements by one
   for (int i = n - 1; i > 0; i--)
      arr[i] = arr[i - 1];
   //Replacing the first array element by temp
   arr[0] = temp;
}

int main() {
   int arr[] = {1,2,3,4,5,6};
   int n = sizeof(arr) / sizeof(arr[0]);

   printf("Array given in input is\n");
   for (int i = 0; i < n; i++)
      printf("%d ", arr[i]);

   rotateRight(arr, n);

   printf("\nArray after rotation is\n");
   for (int i = 0; i < n; i++)
      printf("%d ", arr[i]);

   return 0;
}
Output: 
Array given in input is
1 2 3 4 5 6 
Array after rotation is
6 1 2 3 4 5

Let’s discuss the complexities of method one:

Time Complexity:  O(n), where n refers to the number of elements in the array.

You need to iterate through all the elements so time complexity is O(n).

Space Complexity: O(1) As we are not taking any extra space here.

Method 2: Using Two Pointers

We can accomplish circular right rotation of an array using two pointers, i and j. You will understand it better by going through the below steps:

Step1: Take two pointers i and j.i will point at the starting index of the array, and j will indicate at the end index of the array.

Step 2. Swap arr[i] and arr[j].

Step 3. Now move the i pointer forward and keep the j pointer fixed.

Repeat this process until i is less than j, this will ensure that the elements till index i are placed at the desired position.

Let’s code this approach now.

C++ Program for Circular Right Rotation of an Array

#include <iostream>
using namespace std;

//function to rotate the array clockwise 
void rotateRight(int arr[], int n) {
    //i pointing to the starting element of the array 
    //j pointing to the last element of the array
    int i = 0, j = n - 1;
    while (i != j) {
        //swapping the elements
        swap(arr[i], arr[j]);
        i++;
    }
}

int main() {
    int arr[] = {1,2,3,4,5,6};
    
    //finding size of the array 
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Array given as input is \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    rotateRight(arr, n);

    cout << "\nArray after rotation is\n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}
Output: 
Array given as input is 
1 2 3 4 5 6 
Array after rotation is
6 1 2 3 4 5

Java program for Circular Right Rotation of an Array

import java.util.Arrays;
public class Rotating {
    static int arr[] = new int[] {1,2,3,4,5,6};

    //function to rotate the array clockwise 

    static void rotateRight() {
        //i pointing to the starting element of the array 
        //j pointing to the last element of the array
        int i = 0, j = arr.length - 1;
        while (i != j) {
            //swapping the elements
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
        }
    }

    public static void main(String[] args) {
        System.out.println("Array given in input is");
        System.out.println(Arrays.toString(arr));

        rotateRight();

        System.out.println("Array after rotation is");
        System.out.println(Arrays.toString(arr));
    }
}
Output: 
Array given as input is 
1 2 3 4 5 6 
Array after rotation is
6 1 2 3 4 5

Let’s discuss the time and space complexities of this approach.

Time Complexity:  O(n), where n refers to the number of elements in the array.

You need to iterate through all the elements, so time complexity is O(n). Space Complexity: O(1) As we are not taking any extra space here.

Frequently Asked Questions

What is meant by the left rotation of the array?

Left rotation of an array refers to the anti clockwise rotation of array elements.

Can I rotate an array circularly by more than one element?

Yes! You can rotate the array circularly by any number of elements you want.You can also rotate that clockwise or anticlockwise.

Can I rotate an array of characters?

Yes you can rotate an array of characters with the same approach we have discussed above for an array of integers.

Can I rotate an array circularly towards the right in less than O(N) time complexity?

No, You can’t rotate an array in less than O(N) time complexity because you need to traverse the whole array for rotating an array circularly.

Key Takeaways

In this blog, we discussed two approaches for the circular right rotation of an array. The right rotation of an array implies that you have to rotate the array clockwise. You can rotate array elements circularly by any number of elements. The two-pointer approach is more accessible to implement than the first approach, but the time complexity of both methods will be O(N). After reading this blog, try to solve this problem on your own because you will become good at problem-solving only through practice. Happy Coding!

By: Deeksha Sharma

Exit mobile version