class Solution {
public:
    // Works, but it's slow.
    /*int gcd(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        if (a == b) return a;
        if (a  > b) return gcd(a-b, b);
        else        return gcd(a, b-a);
    }*/

    // Much faster than the above implementation.
    int gcd(int a, int b) {
        if (b == 0) return a;
        else        return gcd(b, a%b);
    }

    void rotate(vector<int>& nums, int k) {
        const size_t N = nums.size();
        if ((N <= 1) || (k == 0)) {
            return;
        }
        // Original algorithm only works for (N,k) coprime.
        // Break the cycles when we complete a loop around the array.
        const int gcdNk = gcd(N,k);
        const int steps = (gcdNk != 1) ? (N / gcdNk) : N;
        int start = -1;
        for (size_t n = 0; n < N; n += steps) {
            ++start;
            int i = start;
            int i_val = nums[i];
            for (size_t s = 0; s < steps; ++s) {
                const int next = (i+k) % N;
                std::swap(i_val, nums[next]);
                i = next;
            }
        }
    }
};