You spin me right round

In 2010 when I started my bachelor's study I was quite shocked by the speed of our education — many courses did not have any gentle introduction and I had to just dive in at once. The first case was with the «Algorithms in C» course, which was actually my first good programming course (and I did not know a thing about C language back then). The course was given by Vladimir Mikhailovich Staroverov and one can even look through the course lecture notes, although without English translation.

I only knew a bit of Pascal back then and it was quite a task for me to master some basics of C quickly since we had to solve some algorithmic tasks in C. Moreover I had no idea about algorithms and complexity analysis. Still, it was very fun, I remember how I spent the whole evening after classes to understand merge sort with recursion.

We had several hours to learn the syntax and then we mainly focused on algorithms and their complexity (time and space). In today's article I would like to tell about an interesting task that I had to solve in this course, it seemed quite difficult for me back then, but now I like to use it as a demonstration of the beauty of algorithms. So here is the task:

You have to create a procedure to rotate an array of length n cyclically by k steps to the right (i.e. clockwise on k steps, 0 <= k < n). The time complexity of the algorithm should be O(n) and the space complexity O(1).

Sounds easy if you do not pay attention to the complexity requirements, right? So my first two ideas looked something like this (this is certainly not C, but whatever):

So the first function uses O(1) memory, but it works in O(k*n), which is not what we wanted. The second one uses only O(n) time to execute but requires some memory. The naive approach did not work out, and the difficult part was also that I had to write it in C back then and I was not any good at it yet (not like I am good with C now, but I love it and use it in my work).

Anyway, I asked for a hint and my teacher told me that this task has two solutions: «the beautiful one» and «the smart one» and told me to choose which one I want to know. I've chosen the beautiful one and will describe it in more detail here, although I will outline my guess on the smart one at the end.

The main trick here is visualization. Imagine an array as a circle on a plane that we actually try to turn clockwise on k steps. Geometry tells us that any rotation on a plane is a combination of two reflections and you can find simple proof of this beautiful fact here. I did not know that proof yet back then, so I just started testing out this idea «with bare hands». Let's look at an example, suppose we have 7 elements in an array we need to rotate 4 steps to the right. Let's draw it on a plane and select a first reflection axis like this:

After making the first reflection we only have to find the new axis for the second one (since math tells us it should work), imagine we do it like this:

After performing this reflection we will get the desired result:

Seems to be working, but how do we select the first and second axis? First, we draw a line from the element number 1 in the array (and it can either intersect or not intersect another element in the circle on the plane, depending on the even/odd size of the array), and then we use the axis through element k//2 from the beginning to make the second reflection. Geometry gave us a useful fact to be sure that these rotations are correct, but to see one more possible explanation, please refer to this article. The math there is very simple and based on modulo arithmetics. Let's take a look at the code:

For me this is actually a very elegant thing, geometric facts helped us to make an effective algorithm. But what about the «smart way»? I only have a hypothesis of what my teacher meant by this and here it goes. The thing is, a cyclic rotation is simply a permutation and to perform it we need to traverse all the possible cycles. And cycles can appear only in cases when n is divisible by k. So there is nothing especially smart here, just the following way of traversal:

That's all about this task, it was quite tough for me in 2010 and I enjoyed solving it eventually, as well as many other tasks (and got a good grade for the course, yes). You may wonder why is this actually a good thing and where would we need such cyclic rotations. Well, the first thing that came to my mind is computer graphics tasks (i.e. fast image scrolling when the image is a set of vectors). If you have other good applications for these algorithms, please fill free to write me in the comments.

Subscribe to my blog and stay tuned for new posts. Thanks for reading, wish you all the best!