I've been recently solving various programming tasks. One that I found was rather easy - array circular rotation. I've chosen C++ as a language and I'd like to keep it.
The idea is to rotate each array element right by a given number of places: e.g. [3, 8, 9, 7, 6] rotated 3 times gives [9, 7, 6, 3, 8].
It wasn't so difficult to figure out solution using extra array. The only required think was new position calculated:
(old_position + rotations)%array_size
However, I've started to think how (if) it can be achieved only with one array? My initial idea was to just swap two elements between new and old position (knowing what old position was) and repeat it for all elements. My code looks like that:
int temp_el;
int temp_index = 0;
int new_pos;
for(int i=0;i<A.size();i++)
{
new_pos = (temp_index + rotations)%A.size();
temp_el = A[new_pos];
A[new_pos] = A[0];
A[0] = temp_el;
temp_index = new_pos;
}
but I forgot about case where in the middle or at the beginning of rotations element at 0 is correct. Which element next I need to pick next? I cannot just take ith element, because it might be already moved.
