Hints for Problems 1 - 100.
Posted: Mon Feb 28, 2022 4:56 am
I am new to Project Euler and am solving the problems in-order 1,2,3, ... While some problems in 1 - 100 have editorials written, I was thinking what about some hints. We already have tags, but their purpose is to not be too much of a hint.
For example. for problem 1: (hidden text, that can be unlocked with a mouse over)
1. O(n):
Simple brute-force.
2. O(1):
(a) Figure out the closed form for the sum of S = {1,2,3,...,N}.
(b) Using (a) figure out the closed form for sum of all multiples of k < M.
(c) Note that 3 and 5 are co-prime, i.e. Greatest Common Divisor(3,5) = 1.
(d) Use the principle of inclusion-exclusion together with (a), (b) and (c) for an O(1) closed form solution.
For example. for problem 1: (hidden text, that can be unlocked with a mouse over)
1. O(n):
Simple brute-force.
2. O(1):
(a) Figure out the closed form for the sum of S = {1,2,3,...,N}.
(b) Using (a) figure out the closed form for sum of all multiples of k < M.
(c) Note that 3 and 5 are co-prime, i.e. Greatest Common Divisor(3,5) = 1.
(d) Use the principle of inclusion-exclusion together with (a), (b) and (c) for an O(1) closed form solution.