CODEWITHSUNDEEP
perl
Steve P.
Steve P.

Reputation: 14699

Trying to figure out if there's a shorter/better way to implement a conditional-sum-like function

Warning: Project Euler Problem 1 Spoiler

I recently discovered Project Euler and decided to try a few of the problems. The first problem was to sum the numbers from 0-999 that are multiples of 3 or 5.

My first, "java-like" solution was: 

print threeAndFive(1000)."\n";

# Returns the sum of the numbers less than $max that are multiples of 3 or 5
sub threeAndFive
{
    my $max = shift;
    my $sum = 0;

    for (my $i=; $i < $max; $i++)
    {
        $sum+=$i if (validate($i)); 
    }   

    return $sum;
}

sub validate
{
    my $num = shift;

    if ($num % 3 == 0 || $num % 5 == 0)
    {
        return 1;
    }

    return undef;
}

I then rewrote it in a more perlish fashion: 

print eval(join ('+', map {($_ % 3 == 0 || $_ % 5 == 0) ? $_ : ()} (1 .. 999)));

While this is obviously way more concise than the original code, I feel that it can probably be shorter or done in a better fashion. For example, in Python, one can do:

print sum([i for i in range(1,1000) if i%3==0 or i%5==0])

Are there more concise/better/clearer ways to do this? Or other equivalent ways that use different functions? I'm interested in learning as much perl as I can, so the more solutions, the merrier.

Thanks in advance.

Upvotes: 2

Views: 96

Answers (2)

ikegami
ikegami

Reputation: 385789

The Straightforward Approach

To answer your question, List::Util provides sum.

use List::Util qw( sum );

Or you could write your own

sub sum { my $acc; $acc += $_ for @_; $acc }

Then you get:

say sum grep { $_ % 3 == 0 || $_ % 5 == 0 } 0..999;

Of course, that's an unoptimised approach.

The Optimised Approach

You can easily reduce the above to Ω(1) memory from Ω(N) by using a counting loop.

my $acc;
for (1..999) { $acc += $_ if $_ % 3 == 0 || $_ % 5 == 0; }
say $acc;

But that's far from the best, since the result can be obtained in Ω(1) time and memory!

This is done by adding the sum of the multiples of 3 to the sum of the multiples of 5, then subtracting the sum of the multiples of 15, because the sums of the multiples of $x can be calculated using

( sum 1..floor($n/$x) ) * $x    # e.g. 3+6+9+... = (1+2+3+...)*3

which can take advantage of the formula

sum 1..$n = $n * ($n+1) * 0.5

Upvotes: 6

perreal
perreal

Reputation: 97948

Less concise, but faster:

sub sum1toN { my $N = int(shift); ($N * ($N+1)) / 2; }
my $N = 999;
print sum1toN($N/3)*3 + sum1toN($N/5)*5 - sum1toN($N/15)*15, "\n";

The sum1toN function computes the sum of integers from 1 to N.

Since:

3 + 6 + 9 + 12 ... + 999

Equals:

(1 + 2 + 3 + ... 333 ) * 3

We can computes sum of multiples of 3 using sum1toN(N/3) * 3. And the same applies to 5. Note that since we count the multiples of by 15 in both cases, a subtraction of sum1toN(N/15)*15 is needed.

Upvotes: 5

Related Questions