Cyclic Right Rotation

Problem Description:

Given an array of integers, perform cyclic right rotation by a specified number of positions. A right rotation means that each element in the array is shifted one position to the right, and the last element of the array is moved to the first position. This process is repeated for the given number of rotations.

Input:

• An array of integers arr[] of size n.
• An integer k, which represents the number of positions to rotate the array to the right.

Output:

• The array after performing k right cyclic rotations.

Constraints:

• 1 <= n <= 10^5 (Length of the array can be up to 100,000 elements)
• 0 <= k <= 10^6 (The number of rotations can be large, so it is recommended to optimize for large k)

Solution:

import java.util.Arrays;

public class CyclicRotation {

    // Solution method that accepts input and returns the rotated array
    public static int[] solution(int[] arr, int k) {
        int n = arr.length;

        if (n == 0 || k == 0) return arr;

        k = k % n;  // In case k is greater than n

        reverse(arr, 0, n - 1);  // Reverse the entire array
        reverse(arr, 0, k - 1);  // Reverse the first 'k' elements
        reverse(arr, k, n - 1);  // Reverse the remaining elements

        return arr;  // Return the rotated array
    }

    // Helper method to reverse a portion of the array from 'start' to 'end'
    private static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start++] = arr[end];
            arr[end--] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2;  // Number of rotations

        // Call solution method and store the result
        int[] rotatedArray = solution(arr, k);

        // Output the rotated array
        System.out.println("Array after " + k + " right rotations: " + Arrays.toString(rotatedArray));
    }
}

        

• Reverse the entire array. This gives us an array where the last element is in the front and vice versa.
• Reverse the first k elements. This moves the elements to their correct positions.
• Reverse the remaining n - k elements. This places the remaining elements in the correct order.

Time and Space Complexity:

Time Complexity:

• Reversing an array or a portion of it takes O(n) time.
• Since the algorithm involves three reversals, the overall time complexity for both right and left rotations is: O(n), where n is the length of the array.

Space Complexity:

• The algorithm operates in-place, meaning it does not use any extra space other than a few variables. Therefore, the space complexity is: O(1).