ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

Published at Jul 13 2018
·
6 comments

Instructions

Test suite

Solution

Given a number, find the sum of all the unique multiples of particular numbers up to but not including that number.

If we list all the natural numbers below 20 that are multiples of 3 or 5, we get 3, 5, 6, 9, 10, 12, 15, and 18.

The sum of these multiples is 78.

For installation and learning resources, refer to the exercism help page.

For running the tests provided, you will need the Minitest gem. Open a terminal window and run the following command to install minitest:

```
gem install minitest
```

If you would like color output, you can `require 'minitest/pride'`

in
the test file, or note the alternative instruction, below, for running
the test file.

Run the tests from the exercise directory using the following command:

```
ruby sum_of_multiples_test.rb
```

To include color from the command line:

```
ruby -r minitest/pride sum_of_multiples_test.rb
```

A variation on Problem 1 at Project Euler http://projecteuler.net/problem=1

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

```
require 'minitest/autorun'
require_relative 'sum_of_multiples'
# Common test data version: 1.1.0 df076b2
class SumOfMultiplesTest < Minitest::Test
def test_multiples_of_3_or_5_up_to_1
# skip
assert_equal 0, SumOfMultiples.new(3, 5).to(1)
end
def test_multiples_of_3_or_5_up_to_4
skip
assert_equal 3, SumOfMultiples.new(3, 5).to(4)
end
def test_multiples_of_3_up_to_7
skip
assert_equal 9, SumOfMultiples.new(3).to(7)
end
def test_multiples_of_3_or_5_up_to_10
skip
assert_equal 23, SumOfMultiples.new(3, 5).to(10)
end
def test_multiples_of_3_or_5_up_to_100
skip
assert_equal 2_318, SumOfMultiples.new(3, 5).to(100)
end
def test_multiples_of_3_or_5_up_to_1000
skip
assert_equal 233_168, SumOfMultiples.new(3, 5).to(1000)
end
def test_multiples_of_7_13_or_17_up_to_20
skip
assert_equal 51, SumOfMultiples.new(7, 13, 17).to(20)
end
def test_multiples_of_4_or_6_up_to_15
skip
assert_equal 30, SumOfMultiples.new(4, 6).to(15)
end
def test_multiples_of_5_6_or_8_up_to_150
skip
assert_equal 4_419, SumOfMultiples.new(5, 6, 8).to(150)
end
def test_multiples_of_5_or_25_up_to_51
skip
assert_equal 275, SumOfMultiples.new(5, 25).to(51)
end
def test_multiples_of_43_or_47_up_to_10000
skip
assert_equal 2_203_160, SumOfMultiples.new(43, 47).to(10000)
end
def test_multiples_of_1_up_to_100
skip
assert_equal 4_950, SumOfMultiples.new(1).to(100)
end
def test_multiples_of_an_empty_list_up_to_10000
skip
assert_equal 0, SumOfMultiples.new().to(10000)
end
# Problems in exercism evolve over time, as we find better ways to ask
# questions.
# The version number refers to the version of the problem you solved,
# not your solution.
#
# Define a constant named VERSION inside of the top level BookKeeping
# module, which may be placed near the end of your file.
#
# In your file, it will look like this:
#
# module BookKeeping
# VERSION = 1 # Where the version number matches the one in the test.
# end
#
# If you are curious, read more about constants on RubyDoc:
# http://ruby-doc.org/docs/ruby-doc-bundle/UsersGuide/rg/constants.html
def test_bookkeeping
skip
assert_equal 2, BookKeeping::VERSION
end
end
```

```
class SumOfMultiples
def self.to(n)
new(3, 5).to(n)
end
def initialize(*factors)
@factors = factors
end
def to(n)
(0...n).select { |x| multiple? x }.inject(:+)
end
private
attr_reader :factors
def multiple?(x)
factors.any? { |f| x % f == 0 }
end
end
```

A huge amount can be learned from reading other peopleâ€™s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

- What compromises have been made?
- Are there new concepts here that you could read more about to improve your understanding?

Level up your programming skills with 3,394 exercises across 50 languages, and insightful discussion with our volunteer team of welcoming mentors.
Exercism is
**100% free forever**.

## Community comments

Using select and then inject like this will create two loops. First, hit every number from 0 to n and pick out the multiples. Then, hit each multiple and add it to the result. In the worst case, looking for multiples of 1, you will double the run time.

Using select and then inject like this will create two loops. First, hit every number from 0 to n and pick out the multiples. Then, hit each multiple and add it to the result. In the worst case, looking for multiples of 1, you will double the run time.

Thanks for the feedback @bcgoss. You haven't made any explicit comments stating whether or not you think my code is inefficient, but I think that is what you were trying to get at. You seem to be suggesting that going over all elements of a set twice is necessarily more inefficient than doing so once. That certainly sounds reasonable doesn't it? You might be surprised to learn than, that turns out not to be the case.

It's actually a common fallacy - and a particularly unfortunate one. In order to explain why things are not as bad as they seem we need to be a bit more precise, so I'm going to be a bit overly verbose, but bare with me.

Using select and then inject like this will create two loops.

Yes, it definitely will. But not firstly that the two loops are not necessarily the same size. This already suggest that we have to be careful about comparing them to a single loop. You are - you note that if we are looking for multiples of 1, the loops will be the same size...

Okay, but is this extra work? If we had a single loop, than we would be doing the both actual work parts, but now are only doing half the work in each loop, so we do exactly the same amount of work overal. Here is a pseudo code example:

## Single loop version

## This does n * (a + b) work

(1..n).times do step_a step_b end

## Double loop version

## This does n * a + n * b work, but that's == n * (a + b)

(1..n).times { step_a } (1..n).times { step_b }

Notice how the total amount of work done stays the same. Now if you were to measure the performance of this, than the second version would be slightly slower. In particular if n, step_a, and step_b are all small, than the first version would be much faster, but of course if that's the case we don't really care about performance anyway. If that's not the case, than the second version will be about as fast as the first version. You might think that there is a lot of overhead because you need to update the loop counter and such, but modern processors are highly vectorized, use branch prediction, and can often update these things in a single instruction concurrently, so you might not even notice the loop "part" itself if this were a language like C/C++.

Note finally that even if we double the running time, that we don't care. Unless we are doing some really cutting edge programming, a constant time difference is not something we optimize for. If we need better performance, than we are almost always better off choosing an algorithm with better asymptotic performance, improving things like read/write times (especially across HDD's or over a network) or just buying a computer that is twice as fast.

The upshot of all of this combined is that if we can make an algorithm more readable by separating the steps than this we should always do this. Only if after profiling we find that a particular piece of code is a bottleneck should we avoid this.

Thanks for your thoughtful reply. I see what you mean, when you frame it as the Distributive Principle it makes a lot of sense. I thought I had profiled but there were some flaws in my approach. I recreated your method, and my method and put a counter inside the block of each one. I read the block out after the method finished with puts. In my implementation, the select block was hidden as a guard statement so I forgot to count it too. Other people might have ignored me, but you took a minute to carefully explain this idea, which I really appreciate!

Cheers @bcgoss, that may be the nicest reply I've ever had :)

Starting the range from the smallest number of factors is more efficient than starting from 0.

Taking the below test as an example: def test_multiples_of_43_or_47_up_to_10000 assert_equal 2_203_160, SumOfMultiples.new(43, 47).to(10000) end

In your solution you are going to check from 0 to 42 if any of these numbers are multiple of the factors, when you have the security it isn't.

@pikislabis commented:

Starting the range from the smallest number of factors is more efficient than starting from 0.

Taking the below test as an example: def test_multiples_of_43_or_47_up_to_10000 assert_equal 2_203_160, SumOfMultiples.new(43, 47).to(10000) end

In your solution you are going to check from 0 to 42 if any of these numbers are multiple of the factors, when you have the security it isn't.

Nice catch! That's indeed an important optimization if the smallest factor is very large. It's maybe not so much of a concern if the smallest factor is 42 and we are generating multiples up to 10_000, but there are certainly situations where it might matter.