[Python] [spoiler] Project Euler Question One- Critique Please

[AnonymousCelt]

The task:
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.

Code: [Select]


def ProblemOne():

i = 0
tally = 0

for i in range(1000):
if i % 3 == 0 or i % 5 == 0:
tally += i

print "My first answer is: %d" % tally




def main():
ProblemOne()


if __name__ == '__main__':
main()


Until I realised how much would be hard coded I[size=78%] considered using the following pattern:[/size]
1,3,5,6,9,10,12,15,18,20,21,24,25,27,30
Skipping by 30 each time but adding 15*i as well as 226.

[Deque]

Just calculate all multiples below 1000 instead of checking all numbers if they are multiples.

[AnonymousCelt]

Just calculate all multiples below 1000 instead of checking all numbers if they are multiples.

Thank you very much for the feedback, do you mean like this?

Code: [Select]


def ProblemOne():

i = 0
tally = 0
increments = 0

for i in range(0,1000,3):
if i % 5 != 0:
tally += i

for i in range(0,1000,5):
tally += i;

print "My first answer is: %d" % tally




def main():
ProblemOne()


if __name__ == '__main__':
main()


I used the two loops to ensure it doesn't add some numbers twice (such as 15) without needing to use any more memory.

[Deque]

Looks good, yes. Did it work?

[Psycho_Coder]

In python its a single line solution :-

Code: [Select]

sum(i for i in range(1000) if i % 3 == 0 or i % 5 == 0)
or

Code: [Select]

sum(i for i in range(1000) if not i % 3 or not i % 5)

[Psycho_Coder]

Think Logically and a bit mathematically as well.

How many multiple of 3 are present within 1000 --> int(999 / 3) = 333 i.e {3, 6, ... 15, ... 30, ... 999) 
How many multiple of 5 are present within 1000 --> int(995 / 5) = 199 i.e. {5, 10, ... 15... 25, 30, ... 995}

Now subtract the number of common multiples that is 15. So, how many multiples of 15 are present ? ---> 66.

Now all of these are in A.P series. So what you can do is calculate the sum of these AP series and get the result.

The Formula for Sum of A.P. Series (3 variations are there but I will use a only one)

Sum_N_Terms = N * (A + L) / 2

where N = No of terms, A = First Term, L = Last term

Therefore the complete workout would be :-

{333 * (3 + 999) / 2} + {199 * (5 + 995) / 2} - {66  * (15 + 990) / 2} = 233168

Pretty Easy

Now how is it an improvisation ?

The Bruteforce way would be to loop from 1 - 999 and check for multiplicity of 3 and 5 and then add. So the loop run for 999 times. But in the second case its just -> 333 + 199 + 66 = 598

So 401 loop cycles are saved.

Before solving any Project Euler problem always try to keep a mathematical mind and it will help a lot


EDIT:-

Python Code. (Here we use python builtin sum function)

Code: [Select]

sum(i for i in range(3, 1000, 3)) + sum(i for i in range(5, 996, 5)) - sum(i for i in range(15, 991, 15))


[AnonymousCelt]

Looks good, yes. Did it work?

Yep, thanks for the pointer.

Think Logically and a bit mathematically as well.

How many multiple of 3 are present within 1000 --> int(999 / 3) = 333 i.e {3, 6, ... 15, ... 30, ... 999) 
How many multiple of 5 are present within 1000 --> int(995 / 5) = 199 i.e. {5, 10, ... 15... 25, 30, ... 995}

Now subtract the number of common multiples that is 15. So, how many multiples of 15 are present ? ---> 66.

Now all of these are in A.P series. So what you can do is calculate the sum of these AP series and get the result.

The Formula for Sum of A.P. Series (3 variations are there but I will use a only one)

Sum_N_Terms = N * (A + L) / 2

where N = No of terms, A = First Term, L = Last term

Therefore the complete workout would be :-

{333 * (3 + 999) / 2} + {199 * (5 + 995) / 2} - {66  * (15 + 990) / 2} = 233168

Pretty Easy

Now how is it an improvisation ?

The Bruteforce way would be to loop from 1 - 999 and check for multiplicity of 3 and 5 and then add. So the loop run for 999 times. But in the second case its just -> 333 + 199 + 66 = 598

So 401 loop cycles are saved.

Before solving any Project Euler problem always try to keep a mathematical mind and it will help a lot


EDIT:-

Python Code. (Here we use python builtin sum function)

Code: [Select]

sum(i for i in range(3, 1000, 3)) + sum(i for i in range(5, 996, 5)) - sum(i for i in range(15, 991, 15))


Will keep that in mind for future, thank you very much.