Skip to content

Instantly share code, notes, and snippets.

@aoloe aoloe/README.md
Created May 30, 2018

Embed
What would you like to do?

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:

// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.