# 8ms, fast C solution

• Time complexity: O(n), n swaps at most, n/2 swaps at least (while k = n / 2),

Space complexity: O(1)

Suppose A = [1,2,3,4,5,6], it costs 2 steps to rotate A to right by k = 2 times, as below:

1. switch [1,2] and [5,6]: A = [5,6,3,4,1,2]
2. switch [3,4] and [1,2]: A = [5,6,1,2,3,4]

Suppose A = [1,2,3,4,5,6], it costs 1 steps to rotate A to right by k = 3 times, as below:

1. switch [1,2,3] and [4,5,6]: A = [4,5,6,1,2,3]

Suppose A = [1,2,3,4,5,6,7], it costs 4 steps to rotate A to right by k = 3 times, as below:

1. switch [1,2,3] and [5,6,7]: A = [5,6,7,4,1,2,3]
2. switch [4] and [3]: A = [5,6,7,3,1,2,4]
3. switch [3] and [2]: A = [5,6,7,2,1,3,4]
4. switch [2] and [1]: A = [5,6,7,1,2,3,4]

Code is:

``````void swap(int* a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}

void rotate_begin_and_end(int* a, int total_size, int rotate_size) {
for (int i = 0; i < rotate_size; ++i) {
swap(a, i, total_size - rotate_size + i);
}
}

void rotate(int* a, int total_size, int right_size) {
if (total_size <= 0 || right_size <= 0) {
return;
}

right_size %= total_size;
int left_size = total_size - right_size;
if (left_size > right_size) {
rotate_begin_and_end(a, total_size, right_size);
rotate(a + right_size, left_size, right_size);
} else if (left_size < right_size) {
rotate_begin_and_end(a, total_size, left_size);
rotate(a, right_size, right_size - left_size);
} else {
rotate_begin_and_end(a, total_size, right_size);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.