Java Solution to Codility’s Cyclic Rotation Problem

June 25, 2018

Hey Developer,

I am continuing my quest to provide you with high quality Java solutions to some of Codility’s coding challenges. Today, I am solving cyclic rotation which can be found here.

My solution has runtime of O(N) and space complexity of O(N) as I am using a second array to solve the problem. The key to solving this problem is properly using the modulo ‘%’ operator, which gives you the remainder after a division. Let’s dive in!

Explanation:

If K % N == 0, then after K rotations, the array would be exactly the same as the array we started with.

If K > N, then we can reduce the value of K, so that we don’t have to do unnecessary work.

For example: if N = 5; K = 99; then K = 99 % 5 = 4; This means that if we rotate the array 4 times or 99 times, our result would be exactly the same. Lets just do less work!

The last step is to simply iterate through rotated_A, and fill it with the rotated values from A.

Below is the code for my Java solution.

class Solution {
	public int[] solution(int[] A, int K) {
	// Create a second array 
        int [] rotated_A = new int[A.length];
        // number of elements in A
        int N = A.length;
        // if A is empty OR has 1 element OR the number of rotations would simply return the original array
        if (N == 0 || N == 1 || K % N == 0) {
        	return A;
        }
        else {
        	// modify K to avoid wasting processing time
        	if (K > N) {
        		K = K % N;
        	}
        	// iterate through rotated_A and populated with the rotated values from A
        	for (int i = 0; i < N; i++) {
        		// if the elements are being moved from right to left (Cyclic rotation)
        		if (N - K + i < N) {
        			rotated_A[i] = A[N - K + i];
        		}
        		// if the elements are being moved from left to right (left to right rotation)
        		else {
        			rotated_A[i] = A[i - K];
        		}
        	}
        	return rotated_A;        	
        }
    }
}