Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I am doing Project Euler problem #6. This is the question it asks:

The sum of the squares of the first ten natural numbers is,

$$1^2 + 2^2 + \ldots + 10^2 = 385$$

The square of the sum of the first ten natural numbers is,

$$(1 + 2 + \ldots + 10)^2 = 55^2 = 3025$$

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

My implementation in Python is as follows:

def sum_of_squares(n):
    return sum([i**2 for i in range(1, n+1)])

def square_of_sum(n):
    return sum(range(1, n+1)) ** 2

print square_of_sum(100) - sum_of_squares(100)

It works but I was wondering if my implementation is good and fast enough?

share|improve this question

3 Answers 3

up vote 5 down vote accepted

Implementation is good indeed, but I have some reservations calling it fast. Its complexity is O(n). As usual (including, but not limited to, Project Euler), an ultimate optimizer is math. Recall that

$$ 1 + 2 + \ldots + n = \frac{n(n+1)}{2}$$

and

$$ 1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}$$

so the result

$$ \frac{n^2(n+1)^2}{4} - \frac{n(n+1)(2n+1)}{6} = \frac{(n-1)n(n+1)(3n+2)}{12}$$

can be achieved in O(1) time.

share|improve this answer
    
Btw. this might be a spoiler for a different Euler problem. I've often seen same problems with increased difficulty on the site. –  domen Jul 30 at 9:06
    
+1 for "ultimate optimizer is math"! –  jonrsharpe Jul 30 at 13:08
    
This is great! Thanks –  user49487 Jul 30 at 17:14

Your implementation looks fine. This calculation is so trivial for a computer to do that it's not worth spending much time optimizing the implementation.

That said, the fact that you called print without parentheses indicates that you are using Python 2. In Python 2, xrange() would be slightly preferable to range().

Alternatively, keep using range(), and call print() with parentheses to make your program compatible with Python 3.

share|improve this answer
    
Or use a from __future__ import print_function. –  Yuushi Jul 30 at 3:30

One minor tweak I would suggest to your current implementation:

def sum_of_squares(n):
    return sum([i**2 for i in range(1, n+1)])

You don't need to built the list; sum will take the bare generator expression as an argument:

def sum_of_squares(n):
    return sum(i**2 for i in range(1, n+1)) # or xrange in 2.x

This will be quicker and also uses less memory (see e.g. here).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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