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

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>

// Complexity: runtime O(n2), memory O(1)
std::pair<int, int> two_sum(const std::vector<int>& numbers, const int x) {

    for (int i = 0; i < numbers.size(); i++){
        for (int j = i + 1; j < numbers.size(); j++){
            int val0 = numbers[i];
            int val1 = numbers[j];
            if (val0 + val1 == x){
                std::cout << "Encontrados! val0: " << val0 << ", val1: " << val1 << std::endl;
                std::pair<int, int> result(val0, val1);
                return result;
            }
        }
    }
}
//Comments: brute-force or naïve approach


// Complexity: runtime O(n), memory O(n)
std::pair<int, int> two_sum_hashset(const std::vector<int>& numbers, const int x) {

    std::unordered_set<int> hashset;

    for (int i : numbers){
        int complement = x - i;
        if (hashset.count(complement) == 1){
            std::pair<int, int> result(complement, i);
            return result;
        }
        hashset.insert(i);
    }
}

/*
Now we want to return the indexes in which these two numbers are:
*/
// Complexity: runtime O(n), memory O(n)
std::pair<int, int> two_sum_hashmap(const std::vector<int>& numbers, const int x) {

    std::unordered_map<int, int> hashmap;

    for (int i = 0; i < numbers.size(); ++i) {

        int current = numbers[i];
        int complement = x - current;

        if (hashmap.count(complement)) {
            std::pair<int, int> result{hashmap[complement], i};
            return result;
        }

        hashmap[current] = i;
    }
}


//Comments: int 4bytes = 32 bits = 4*10^9 -> [-2*10^9, +2*10^9]
/*
 char 1 byte
 int 4 bytes
 long  8 bytes
 float 4 bytes
 double 8 bytes
 bool 1 byte

 ...const int x)   <- 4 bytes
 ...const int& x)  <- 8 bytes


 ...const imagen y) <-- 100000 bytes
 ...const imagen& y) <-- 8 bytes
*/

int main(){

    std::vector<int> nums_1 = {1, 2, 3};
    int x1 = 3;
    std::pair<int, int> result_1 = {1, 2};

    std::vector<int> nums_2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int x2 = 17;
    std::pair<int, int> result_2 = {8, 9};

    std::cout<<"Test 1: "<<std::endl;
    auto res_1_berta = two_sum_hashset(nums_1, x1);

    if (res_1_berta == result_1) {
        std::cout<<"Bien!"<<std::endl;
    } else {
        std::cout<<"Mal!"<<std::endl;
    }

    std::cout<<"Test 2: "<<std::endl;
    auto res_2_berta = two_sum_hashset(nums_2, x2);

    if (res_2_berta == result_2) {
        std::cout<<"Bien!"<<std::endl;
    } else {
        std::cout<<"Mal!"<<std::endl;
    }

    return 0;
}

/*
std::vector<int> numeros = "902183901234031892748923651";
int x;

Como harias una funcion que te devuelva dos numeros del vector cuya suma sea x? Asumir que hay siempre solucion.
Aunque haya mas de una solucion devolver una.

*/