Showing posts from September 24, 2017

Sum of multiples problem

One of the problems generalizes a Project Euler problem: what's the sum of multiples of 3 and 5 less than 1000? Seems simple enough:
sum [3, 6..999] + sum [5, 10..999] but that's too big; it counts some values twice. With a little thought, though, you'll realize that the duplicates are the multiples of 15, so
sum [3, 6..999] + sum [5, 10..999] - sum[15, 30..999] will do the trick. Why 15? Well, it's 3 * 5... but more on that later.

The problem makes the upper bound a parameter, and allows an array (or list, depending on the language) of factors. Looking around (which you can do on the site after you've submitted your own solution), one sees two typical approaches:
Go through [1..limit - 1], pick out the values that are multiples of one or more of the factors, and add up the result.Create a set or hash table from [[f, 2*f..limit - 1] f <- factors] (thus getting rid of the duplicates), and add up the elements of the set/keys of the hash table.…