Project Euler 1:Find the sum of all the multiples of 3 or 5 below 1000
Much faster (constant time) answer:
def sum_multiples(multiple, to)
n = (to-1) / multiple
n * (n+1) / 2 * multiple
end
irb(main):001:0> sum_multiples(3, 10) + sum_multiples(5, 10) - sum_multiples(15, 10)
=> 23
irb(main):002:0> sum_multiples(3, 1000) + sum_multiples(5, 1000) - sum_multiples(15, 1000)
=> 233168
Why does this work? sum_multiples
works out the sum of multiples of multiple
up to but not including to
(it relies on integer division). It first works out the number of number of multiples being summed (n
), then multiples the standard formula for the sum of 1..n = n(n+1)/2 by multiple
. Using this, we can add together the sums for the multiples of 3 and 5. We must then not forget that some numbers are multiples of both 3 and 5, so we subtract multiples of 15 (3*5).
Although your answer is more than fast enough for the constraints in this problem (it should run in about 1 millisecond on modern hardware), a faster solution such as the one I provide will give a result on very large numbers.
Sum of all the multiples of 3 or 5 below 1000 gives a wrong answer in C
Some numbers will be divisible by both 3 and 5, you should not add them twice.
A code like this will give correct result:
long int x,total = 0;
for(x = 0; x < 1000; ++x)
{
if(x % 3 == 0)
total = total + x;
else if(x % 5 == 0)
total = total + x;
}
printf("%ld", total);
in the code above if else if
make sure that if a number is divisible by 3 or by 5. And allow to sum up on this basis.
It can further be optimized to:
for(x= 0; x < 1000; ++x)
{
if(x%3 == 0 || x%5 == 0)
total = total + x;
}
Above solution is O(n) for better time complexity O(1) we can use
Arithmetic Progression with interval of 3 and 5.
n = total number of multiples of given number(Num) in given range (1...R). in this case (1...1000)
a1 = first multiple. Here it will be 3 or 5.
an = last multiple. i.e 3Xn
Hence, following code will calculate Sum of series with interval 3/5 (Num) for given range 1...lastOfRange (excluding lastOfRange).
long SumOfSeries(long Num, long lastOfRange)
{
long multiplesCount = (lastOfRange-1) / Num; //(lastOfRange-1) to exlude the last number 1000 here
long result = multiplesCount * (Num + (multiplesCount * Num)) / 2;//Num = a1, (multiplesCount * Num) = an.
return result;
}
and this can be called as:
long N = 1000;
Sum = SumOfSeries(3, N) + SumOfSeries(5, N) - SumOfSeries(3*5, N);
printf("%ld", total);
Finding multiples of 3 or 5 below 1000
Your code will generate duplicate values. For example, 15 is multiple of both 3 and 5. Hence, you are adding duplicate values to the sum every time a number is multiple of both 3 and 5. The code below fixes your issue.
multiple1 = 5
multiple2 = 3
index = 1
sum = 0
while multiple1 < 1000 or multiple2 < 1000:
multiple1 = 5 * index
multiple2 = 3 * index
if (multiple1 < 1000) and (multiple1 % 3 != 0):
sum = sum + multiple1
if (multiple2 < 1000):
sum = sum + multiple2
index = index + 1
print (sum)
Solving Project Euler Problem no.1 (Python)
You can take the iterative approach: O(n)
s35 = sum(n for n in range(1000) if n%3 == 0 or n%5 == 0)
Or you can compute it mathematically: O(1)
n3 = (1000-1)//3 # number of multiples of 3 (includes multiples of 15)
n5 = (1000-1)//5 # number of multiples of 5 (includes multiples of 15)
n15 = (1000-1)//15 # number of multiples of 15 (counted twice)
s35 = n3*(n3+1)//2*3 + n5*(n5+1)//2*5 - n15*(n15+1)//2*15
Find the sum of all the multiples of 3 or 5 below 1000
Two things:
- you're including 1000 in the loop, and
- you're adding one to the sum each time, rather than the value itself.
Change the loop to
for(i=0;i<1000;i++)
And the sum line to
sum=sum+i;
Related Topics
Thread Safety: Class Variables in Ruby
Ruby Hash Default Value Behavior
Why Does My Ruby 'Ri' Tool Not Return Results in Command Prompt
Ruby Source Code Analyzer (Something Like Pylint)
Using Instance Variables in Class Methods - Ruby
Database Configuration Does Not Specify Adapter
"Whenever" Gem Running Cron Jobs on Heroku
How to Change All the Keys of a Hash by a New Set of Given Keys
Ruby: How to Add "# Encoding: Utf-8" Automatically
Couldn't Require Openssl in Ruby
How to Detect Certain Unicode Characters in a String in Ruby
Ruby on Rails - Drop Down Box on Change Event
How to Know When to "Refresh" My Model Object in Rails