// Compiled with: g++ -Wall -std=c++14 -pthread

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//Run-time complexity O(n*k)
//Memory complexity O(1)
// 0 1 2 3 4 k = 0
// 4 0 1 2 3 k = 1
// 3 4 0 1 2 k = 2
// 2 3 4 0 1 k = 3
// 0 1 2 3 4 k = 4
// 4 0 1 2 3 k = 5

//Run-time complexity O(n * min(n,k)) --> at most O(n^2)
void rotate(vector<int>& nums, int k) {
    k = k % nums.size();
    for (int i = 0; i < k; ++i){
        nums.insert(nums.begin(), nums[nums.size() - 1]); //O(n)
        nums.pop_back(); //O(1)
    }
}

// Rotate 2
// {0, 1, 2, 3, 4, 5}
// {4, 5, 0, 1, 2, 3} --- 2 vectors {4, 5}, {0, 1, 2, 3}
// Memory complexity O(n)
// Run-time complexity O(n)
void rotate_2(vector<int>& nums, int k) {
    k = k % nums.size();
    vector<int> first_vector(nums.begin(), nums.end() - k);
    vector<int> second_vector(nums.end() - k, nums.end());

    second_vector.insert(second_vector.end(), first_vector.begin(), first_vector.end()); // O(n_f)

    nums = second_vector;
}

// 1 2 3 4 5 k = 2
// 5 4 3 2 1
// 4 5 3 2 1
// 4 5 1 2 3
// Memory complexity O(1)
// Run-time complexity O(n)
void rotate_3(vector<int>& nums, int k) {
    if (k <= 0)
        return;

    k = k % nums.size();
    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin() + k);
    reverse(nums.begin() + k, nums.end());
}

void print_vector(const vector<int>& vector) {
    for (auto& i : vector) { // const, auto, & || const-> no se pueda modificar | auto = vector<int> | & = ref
        cout << i << " ";
    }
}

int main(){

    vector<int> vec_1 = {1, 2, 3, 4, 5};
    int k1 = 0;
    vector<int> expected_1 = {1, 2, 3, 4, 5};

    vector<int> vec_2 = {1, 2, 3, 4, 5, 6};
    int k2 = 3;
    vector<int> expected_2 = {4, 5, 6, 1, 2, 3};

    vector<int> vec_3 = {1, 2, 3, 4, 5};
    int k3 = 100;
    vector<int> expected_3 = {1, 2, 3, 4, 5};

    vector<int> vec_4 = {1, 2, 3, 4, 5};
    int k4 = 3;
    vector<int> expected_4 = {3, 4, 5, 1, 2};

    vector<int> vec_5 = {1, 2, 3, 4, 5};
    int k5 = 8;
    vector<int> expected_5 = {3, 4, 5, 1, 2};


    vector<vector<int>> expecteds = {expected_1, expected_2, expected_3, expected_4, expected_5};
    vector<vector<int>> vecs = {vec_1, vec_2, vec_3, vec_4, vec_5};
    vector<int> ks = {k1, k2, k3, k4, k5};

    for (int i = 0; i < expecteds.size(); ++i) {
        cout<<" ------- TEST "<<i+1<<" -------"<<endl;
        cout<<"Expected: ";
        print_vector(expecteds[i]);
        cout<<endl<<"Obtained: ";
        rotate_3(vecs[i], ks[i]);
        print_vector(vecs[i]);
        cout<<endl;

    }

    return 0;
}