A left rotation operation on an array of size n shifts each of the array’s elements 1 unit to the left. For example, if 2 left rotations are performed on array [1, 2, 3, 4, 5], then the array would become [3, 4, 5, 1, 2] .
Given an array of n integers a, and a number k, perform k left rotations on the array.

Here we want solutions with O(1) additional space and O(n) time complexity.

My solution

Note that the element at index i is moved to (i-k) % n.
Let n = 15 and k = 6, then

a[0] <- a[6] <- a[12] <- a[3] <- a[9] <- a[0],

a[1] <- a[7] <- a[13] <- a[4] <- a[10] <- a[1],

a[2] <- a[8] <- a[14] <- a[5] <- a[11] <- a[2].

Clearly, it forms 3 circles, and the 3 circles cover all the movement. 3 is the greatest common divisor (gcd) of 15 and 6.

It should be easy to prove that, the rotation can be broken down to g (gcd of n and k) smaller circles, and within every circle are elements at index i, (i+k)%n, … We only need to rotate each circle by one step.

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}

vector<int> array_left_rotation(vector<int> a, int n, int k) {
    if (k==n) return a;
    int g = gcd (n, k);
    for (int j=0; j< g; j++) { 
        int tmp = a[j], i = j, to_i = (i+k)%n;
        while (to_i !=j) {
            a[i] = a[to_i];
            i = to_i;
            to_i = (i+k)%n;
        }
        a[i] = tmp;
    }
    return a;
}

int main(){
    int n;
    int k;
    cin >> n >> k;
    vector<int> a(n);
    for(int a_i = 0;a_i < n;a_i++){
        cin >> a[a_i];
    }
    vector<int> output = array_left_rotation(a, n, k);
    for(int i = 0; i < n;i++)
        cout << output[i] << " ";
    cout << endl;
    return 0;
}

There is another solution from the book, Programming Pearls.

Solution 2

Observation:

for an array {a[0], a[1],… a[k-1], a[k], a[k+1],…a[n-1]}, after the rotation, it becomes {a[k], a[k+1]…a[n-1], a[0], a[1]… a[k-1]}. Let’s notate the a[0]~a[k-1] part as A, the latter part a[k]~ a[n-1] as B. Then what the rotation does is actually transfering AB to BA.

Solution:

First, reverse AB as a whole: AB -> BrAr.
Then, reverse Ar, Br individually: BrAr -> BA

// pay attention to the & in the parameter
void swap(vector<int> &a, int m, int l) {
    int tmp = a[m];
    a[m] = a[l];
    a[l] = tmp;
  }

vector<int> array_left_rotation(vector<int> a, int n, int k) {
    if (k==n) return a;
    // reverse AB as a whole
    for (int i=0; i < n-1-i; i++) {
        swap(a, i, n-1-i);
    }
    // reverse Br
    for (int i=0; i< n-k-1-i; i++) {
        swap(a, i, n-k-1-i);
    }
    // reverse Ar
    for (int i= n-k; i < 2*n-k-i-1;i++) {
        swap(a, i, 2*n-k-i-1);
    }
    return a;
}

This works, but it’s kind of tiring to get all the indices right to the swap() call.
Let’s try with a reverse() helper function. And also, reverse A, B individually first, and then reverse ArBr as a whole, then we get BA.

void reverse(vector<int> &a, int low, int high) {
    while (low < high) {
        int tmp = a[low];
        a[low] = a[high];
        a[high] = tmp;
        low++; high--;
    }
}

vector<int> array_left_rotation(vector<int> a, int n, int k) {
    if (k==n) return a;
    // reverse A
    reverse(a, 0, k-1);
    // reverse B
    reverse(a, k, n-1);
    // reverse ArBr as a whole
    reverse(a, 0, n-1);
    return a;
}