18
\$\begingroup\$

I'm learning C++ and currently doing Project Euler challenges. The first challenge is the following.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

I did a quite simple and stupid brute-force implementation by just looping from 1 to 999, checking if its divisible by either 3 or 5 and if it is, sum it with the result variable.

Is there any faster/better/cleaner implementation, maybe without a loop or with less division?

#include <iostream>

int main(int argc, char *argv[])
{
    int result(0);
    for (int i = 1; i < 1000; ++i) {
        if (!(i % 3 && i % 5)) {
            result += i;
        }
    }
    std::cout << "Result: " << result << "\n";
    return 0;
}
\$\endgroup\$
  • 9
    \$\begingroup\$ The thing about Euler tests is that they are trying to make you think smart. Yes you can brute force this even for large values of n but there should be an elegant solution that even a human could do. It is learning these tricks that will help you in later tests were a brute force attack on the problem is not feasible. \$\endgroup\$ – Martin York Apr 18 at 11:23
  • 3
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Mast Apr 18 at 14:18
  • 1
    \$\begingroup\$ int result(0); and int result=0; are the same, but the latter is more clear (to me at least) \$\endgroup\$ – Stefan Apr 19 at 7:45
22
\$\begingroup\$

The code is basically fine.

The if condition is perhaps a little complicated though. To interpret it you have to read "if not ((i is not a multiple of 3) and (i is not a multiple of 5))", which is a double negative.

Given the problem statement, we'd expect something more like "if (i is a multiple of 3) or (i is a multiple of 5)", so:

if ((i % 3 == 0) || (i % 5 == 0))

Nitpicking:

  • If we don't need argc and argv, we can declare main as int main() with no arguments.
  • The return 0; at the end of main happens automatically in C++, so we don't have to write it ourselves.

Note that there exists an arithmetic solution to the problem, which is much faster (it could even be done at compile-time in C++).

We want to sum all the multiples of 3 or 5 less than 1000. We can think about the sequence of multiples of 3 as (3, 6, 9, 12, 15, ..., 999), which is the same as 3 * (1, 2, 3, 4, 5, ..., 333). [...]

Such a sequence, where the difference between each number is constant, is called a finite arithmetic progression [and the sum is] a finite arithmetic series. The formula for the sum is 1/2 * n * (a_1 + a_n). where n is the number of terms being added, a_1 is the first element in the sequence, and a_n is the last element in the sequence.

\$\endgroup\$
  • 3
    \$\begingroup\$ Even the brute-force formula could easily be done at compile-time, though it's slightly more unwieldy. \$\endgroup\$ – Deduplicator Apr 18 at 10:48
  • 1
    \$\begingroup\$ Is there a difference in speed by not adding argv and argc? \$\endgroup\$ – o2640110 Apr 18 at 12:15
  • \$\begingroup\$ @o2640110 No there is not. :) \$\endgroup\$ – Rakete1111 Apr 18 at 13:45
  • 1
    \$\begingroup\$ The arithmetic solution could be done at compile time, or even worked out on a 4-op calculator. \$\endgroup\$ – Laurent LA RIZZA Apr 19 at 8:04
  • \$\begingroup\$ With the arithmetic solution, you would have to somehow make sure not to count multiples of both 3 and 5 twice. With the brute-force solution, this wouldn't happen. \$\endgroup\$ – John Leuenhagen Apr 21 at 3:21
18
\$\begingroup\$

Yes, there are ways to do this that avoid most of the divisions, and are probably faster as well.

Let's start with a simplified version of the problem: add up all the multiples of 3.

Now, you could do a simplified version of what you've written:

int sum = 0;

for (int i=1; i<1000; i++)
    if (i % 3 == 0)
        sum += i;

...but we know up front that 1 and 2 aren't multiples of three. We can generate all multiples of three by counting by 3's:

int sum = 0;

for (int i=0; i<1000; i += 3)
    sum += i;

Obviously enough, we can do the same thing for multiples of 5:

int sum = 0;

for (int i=0; i<1000; i += 5)
    sum += i;

But if we do both in succession:

int sum = 0;

for (int i=0; i<1000; i += 3)
    sum += i;

for (int i=0; i<1000; i += 5)
    sum += i;

...we'll get the wrong answer. The problem now is that if a number is a multiple of both 3 and 5 (e.g., 15) we've counted it twice. There are a few ways we can avoid that. One is to have the second loop add i to the sum if and only if i is not a multiple of 3.

for (int i=0; i< 1000; i += 5)
    if (i % 3 != 0)
       sum += i;

Another is to initially add those, but then add a third loop that generates only the numbers that are multiples of both 3 and 5, and subtracts those from the overall result:

int product = 3 * 5;

for (int i = 0; i < 1000; i += product)
    sum -= i;

Since you're (apparently) more interested in learning programming than in learning math, I'll only sketch out the next step. There are ways to avoid doing those loops at all though. What we're really doing is (for two different values of N) summing a series of 1N + 2N + 3N + 4N + ...

Using the distributive property, we can turn that into N * (1 + 2 + 3 + 4 + ...). Gauss invented an easy way to sum a series like 1 + 2 + 3 + 4 + ..., so what we need to do is compute the number of terms of that series we need for each of 3 and 5, compute them, multiply by 3 and 5 respectively, and add together the results. Then do the same for multiples of 15, and subtract that from the result. The number of terms in each series we need will be the upper limit divided by the N for that series--so for multiples of 3, we have 1000/3 terms, and for multiples of 5 we have 1000/5 terms.

So, we can compute the final value as:

3 * gauss_sum(1000/3) + 5 * gauss_sum(1000/5) - 15 * gauss_sum(1000/15)

...and we're left with no loops at all, so we can compute the correct value for any upper limit (up to what fits in an unsigned long long, anyway) in constant time.

\$\endgroup\$
11
\$\begingroup\$

The one bit that is absolutely not fine is this line:

if (!(i % 3 && i % 5))

It is clever, and clever is bad. The question was about "all integers that are multiples of 3 or 5." So write that:

if (i % 3 == 0 || i % 5 == 0)
\$\endgroup\$
  • 1
    \$\begingroup\$ +1! Any time you write code that has to be deciphered, you should change it to something that can be read. To be honest, half the time, I'd take it a step further, and actually put i%3 into a variable: divisibleBy3. That way, the IF statement is simply if (divisbleBy3 || divisibleBy5) - doesn't get much more readable than that. \$\endgroup\$ – Kevin Apr 19 at 12:51
  • 2
    \$\begingroup\$ @Kevin: Another possibility would be to define a lambda like: auto divisibleBy = [](int x, int y) { return x % y == 0; }; Then you'd just use: if (divisibleBy(i, 3) || divisibleBy(i, 5)) ... \$\endgroup\$ – Jerry Coffin Apr 19 at 18:37
  • \$\begingroup\$ Just to add to this, you can see the compiler output here. godbolt.org/z/lAws-Z At least for this compiler (clang 7, fully optimised) the two versions compile to exactly the same thing. That all to say, it's OK to use the readable version over what you expect is more efficient: the compiler knows better than almost any human programmer what will be efficient. \$\endgroup\$ – Josiah Apr 20 at 6:52
1
\$\begingroup\$

As you were asking for "less division"... Here's a different approach with absolutely no division, multiplication or modulo operations. We have two counters t (for increment three) and f (for increment five), and update them in a single while loop. Due to the increments it's guaranteed t and f will always be numbers divisible by 3 resp. 5. Now we just have to pick which counter to update (the lower one), and to handle the case when both counters occasionally meet :)

(You can avoid the std::min-line and put the addition to result into the if/else if/else-part, but with this it's easier to understand what happens.)

#include <iostream>

int main() {
  unsigned t=0, f=0;
  unsigned result=0;
  while (t<1000) {
    result+=std::min(t, f);

    if (t<f) t+=3;
    else if (f<t) f+=5;
    else { // f==t
      t+=3;
      f+=5;
    }
  } 
  std::cout << "Result: " << result << std::endl;
  return(0);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You know that return is not a function? That can be crucial in C++ when the return-type is deduced with decltype(auto). \$\endgroup\$ – Deduplicator Apr 20 at 16:48
  • \$\begingroup\$ Yes I know that. @Deduplicator, do you have an example where brackets actually do change the return type? \$\endgroup\$ – jvb Apr 20 at 17:11
  • \$\begingroup\$ Ok, so the deduced function types indeed would be T() vs T&() in your example - actually different in regards to std::type_info, but only in this aspect - and neither deduced type is technically incorrect or leads to erroneous behaviour. As a consequence, I wouldn't encourage comparing type info obtained with auto :) \$\endgroup\$ – jvb Apr 20 at 22:18
  • \$\begingroup\$ std::type_info (returned by typeid) only knows fully decayed types. And if i was not a global, but e.g. a local or parameter, the difference between a copy and a reference may be more relevant. \$\endgroup\$ – Deduplicator Apr 20 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.