README.md

Lists sum problem

You are given two lists a and b with integers, that also can be negative, and a target sum.

Task:

• find a function that returns true if two numbers in the list can be added to build the target sum.

Hints:

• Draw down the problem on paper to solve it
• Think about about different solutions and think about how they differ in runtime if the list would contain 1 Mio. elements

Resources:

• https://en.wikipedia.org/wiki/Subset_sum_problem
• https://rosettacode.org/wiki/Two_Sum
• https://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number

target-sum.cpp

// g++ -std=c++17 -o target-sum target-sum.cpp && ./target-sum

#include <vector>
#include <iostream>
#include <algorithm> // transform
#include <unordered_set>

bool find(int sum, std::vector<int> a, std::vector<int> b)
{
    for (int i: a) {
        for (int j: b) {
            if (sum == i + j) {
                return true;
            }
        }
    }
    return false;
}

bool hashed_find(int sum, std::vector<int> a, std::vector<int> b)
{
    std::unordered_set<int> set(a.size());
    for (int i: a) {
        set.insert(sum - i);
    }
    for (int i: b) {
        if (set.find(i) != set.end()) {
            return true;
        }
    }
    return false;
}

bool hashed_no_loop_find(int sum, std::vector<int> a, std::vector<int> b)
{
    std::transform(a.begin(), a.end(), a.begin(), [sum](int i) { return sum - i; });
    std::unordered_set<int> set{a.begin(), a.end()};
    return b.end() != std::find_if(b.begin(), b.end(), [&set](int i) {auto s = set.find(i); return s != set.end();});
}

int main()
{
    int sum = 12;

    std::vector<int> a = {2, 5, 7, 6, 6};
    std::vector<int> b = {6, 4, 7, 9, 2};

    std::cout << (find(sum, a, b) ? "" : "not ") << "found" << std::endl;
    std::cout << (hashed_find(sum, a, b) ? "" : "not ") << "found" << std::endl;
    std::cout << (hashed_no_loop_find(sum, a, b) ? "" : "not ") << "found" << std::endl;
}