2017-01-13

Solving a HackerRank Problem with Modulo Array Rotation

blogentry, programming, application, apply

banner

On December 25th of 2016, I wrote about AWESOMENESS OF % (MODULO OPERATOR). I was able to apply the knowledge I learned to solve a HackerRank warm-up question, Circular Array Rotation.

The gist of the question is to rotate an array multiple times, given the data from console and then print the output.

It was exactly the situation where I can apply the concept I wrote about in AWESOMENESS OF % (MODULO OPERATOR).

I tried to solve it by rotating it the number of times entered by the user, but the tests were failing for very large input data. Here is the initial implementation.

1private static int[] RotateRightNTimes(int[] a, int k)2{3	int[] result = a;4	for (int rotateIndex = 0; rotateIndex < k; rotateIndex++)5	{6		result = RotateRightOnce(result);7	}8
9	return result;10}11
12private static int[] RotateRightOnce(int[] a)13{14	int[] result = new int[a.Length];15
16	for (int i = 0; i < a.Length; i++)17	{18		result[(i + 1) % a.Length] = a[i];19	}20
21	return result;22}

As shown above, it's very naive implementation of rotating. If I had thought this through, I could have made it faster from the get-go by adding the number of positions to rotate instead of adding 1 in line 18 (result[(i + 1) % a.Length]).

My second approach was just as I describe above and just add number of rotation count.

1private static int[] RotateRightNTimes2(int[] a, int rotateCount)2{3	int[] result = new int[a.Length];4
5	for (int i = 0; i < a.Length; i++)6	{7		result[(i + rotateCount) % a.Length] = a[i];8	}9
10	return result;11}

Now there is only one method and now it takes O(n) to rotate instead of O(N^2).

Full source is available on GitHub.

Conclusion

Being able to apply what I've learned recently and wrote about seems to make a long last memory. I will have to change my approach on learning;I'd learn new things as if I will have to apply it in short or long term.