You are given an expense report by the Elves that looks similar to the following:
1721 979 366 299 675 1456
You are told there is an error in the report and you need to find the two entries that sum to
2020. In this example above, the two entries that sum to
299. Then to submit the final answer to the website, you need to multiply the two entries together.
The Elves are grateful but now they ask you to find three entries that sum to
2020. Then to submit the final answer to the website, you need to multiply the three entries together.
There are a few different solutions, each with different complexities.
# Part 1 - O(n) complexity nums = set([int(x) for x in report.splitlines()]) for num in nums: if (2020-num) in nums: print((2020-num)*num) # Part 2 - O(n^2) complexity for a in nums: for b in nums: if a != b: c = 2020-b-a if c in nums: print(a*b*c) # Part 2 - O(n^3) complexity for a in nums: for b in nums: for c in nums: if a+b+c == 2020: print(a*b*c)