//Runtime complexity O(n^2)
//Memory complexity O(1)
int singleNumber(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(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    if (nums[0] != nums[1]) return nums[0];
    if (nums[size(nums) - 1] != nums[size(nums) - 2]) return nums[size(nums) - 1];
    for (int i = 1; i < size(nums) - 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)
int singleNumber(vector<int>& nums) {
    unordered_map<int, int> hashmap;
    for (int i = 0; i < size(nums); ++i){
        if (hashmap.count(nums[i]) == 0) hashmap[nums[i]] = 1;
        else hashmap[nums[i]] = 2;
    }
    for (auto i: hashmap){
        if (i.second == 1) return i.first;
    }

    return -1;
}

//Runtime complexity O(n)
//Memory complexity O(1)
int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int num: nums){
        result = result ^ num;
    }

    return result;
}