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

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <numeric>

using namespace std;

//Runtime complexity O(n^2)
//Memory complexity O(1)
int singleNumber(const vector<int>& nums) {
    for (int num: nums){
        int times = std::count(nums.begin(), nums.end(), num); //count in vectors is O(n)
        if (times == 1)
            return num;
    }
    return -1;
}

//Runtime complexity O(nlogn)
//Memory complexity O(1)
int singleNumber_2(vector<int>& nums) {
    sort(nums.begin(), nums.end()); //O(nlogn)
    if (nums[0] != nums[1])
        return nums[0];

    if (nums[nums.size() - 1] != nums[nums.size() - 2])
        return nums[nums.size() - 1];

    for (int i = 1; i < nums.size() - 1; ++i){
        if (nums[i] != nums[i-1] && nums[i] != nums[i+1])
            return nums[i];
    }
    return -1;
}

//Runtime complexity O(n)
//Memory complexity O(n)
// hashmap[nums[i]]
// if hashmap does not contain the key nums[i] -> it creates it and returns a reference to the value, which is init to 0;
// if it contains the key -> it returns a reference to the value;
int singleNumber_3(const vector<int>& nums) {
    unordered_map<int, int> hashmap;
    for (int i = 0; i < nums.size(); ++i)
        ++hashmap[nums[i]];

    for (auto& i: hashmap)
        if (i.second == 1)
            return i.first;

    return -1;
}

// Runtime complexity O(n)
// Memory complexity O(1)
// 7 3 7 3 1
// 0 ^ 7 ^ 3 ^ 7 ^ 3 ^ 1
// 0 ^ (3 ^ 3) ^ (7 ^ 7) ^ 1
// 0 ^ 0 ^ 0 ^ 1
// 1
// 0 ^ 7 = 7
// 7 ^ 3 = 111 ^ 011 = 100 = 4
int singleNumber_4(const vector<int>& nums) {
    int result = 0;
    for (int num: nums){
        result = result ^ num;
    }
    return result;
}

int xor(int acc, int new_n) {
    return acc^new_n;
}

int singleNumber_5(const vector<int>& nums) {
    return accumulate(nums.begin(), nums.end(), 0, [](int x, int y) { return x^y;});
}

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> trial1 = {1,2,1,2,4};
    vector<int> trial2 = {1,2,4,2,4};
    vector<int> trial3 = {1,2,1,4,4};

    int result1 = singleNumber_4(trial1);
    int result2 = singleNumber_4(trial2);
    int result3 = singleNumber_4(trial3);

    int expected1 = 4;
    int expected2 = 1;
    int expected3 = 2;

    vector<vector<int>> trials = {trial1, trial2, trial3};
    vector<int> results = {result1, result2, result3};
    vector<int> expecteds = {expected1, expected2, expected3};

    for (int i = 0; i < trials.size(); ++i) {
        cout << " ----  TRIAL " << i + 1 << ". ------" << endl;
        cout << "Vector: ";
        print_vector(trials[i]);
        cout << endl << "Expected result: "<< expecteds[i]<<". Obtained result: "<<results[i]<<endl;

    }


    return 0;
}

//