Problem 6: Sum square difference
This problem is fairly simple, however, it will allow us to explore our good friend recursion. We will use a combination of that and functional programming to solve this fella with relative ease...hopefully. Alright, enough yammering, let's get to it!
Discussion
The sum of the squares of the first ten natural numbers is: 1^2 + 2^2 + ... + 10^2 = 385
The square of the sum of the first ten natural numbers is: (1 + 2 + ... + 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.
Statement
Find the difference between the sum of the squares of the first n natural numbers and the square of the sum.
Video Version
If you like to watch rather than read, check out the video that accompanies this article. If not, keep reading!
Solution
As I mentioned earlier, I chose to use these two things:
- Functional programming
- Recursion
Before we get too deep into the discussion, I want to discuss recursion. If you are already familiar with the concept, feel free to skip over this part.
Recursion
Recursion is simply:
A function calling itself over and over again
It will call itself until one of two things happens:
- We reach the call stack limit.
- We define an exit value.
Example for this Problem
Let's say we want to find out the total of all the squared values up to a given value, i.e. 1^2 + 2^2....n^2. We can write a function that calls itself until a condition has been met. I like to call that the "ceiling," because it usually represents the highest value we don't want to exceed.
// Our function takes in two values:
// our limiter (ceiling) and a total that we will return (inititally set at 0)
function getSumSquares(ceiling, total = 0) {
// check to see if we have reduced our ceiling to zero. If so...escape!
if (ceiling === 0) {
return total;
}
// if we still have more work to do, do the work
let squared = (total += ceiling ** 2);
// call yourself, but reduce our ceiling by one.
return getSumSquares(ceiling - 1, total);
}
getSumSquares(10)
The function is going to call itself until our condition is met, in this case, ceiling === 0
, hence the name recursion.
If you want more detail about recursion, check out my recursion article:
https://dev.to/codenutt/javascript-recursion-explained-in-4-minutes-26oa
Steps
The steps for this problem are fairly simple:
- Calculate the sum of all squares up to
n
- Calculate the square of the summed values up to
n
- Calculate the difference between the two.
Solution
As I mentioned earlier, we will be composing our solution via functional programming. That means we will be creating three separate functions. The first one we already did in the discussion about recursion!
Sum of all Squares
function getSumSquares(ceiling, total = 0) {
if (ceiling === 0) {
return total;
}
total += ceiling ** 2;
return getSumSquares(ceiling - 1, total);
}
Square of all Sums
function getSquareSum(ceiling, total = 0) {
if (ceiling === 0) {
return total ** 2;
}
total += ceiling;
return getSquareSum(ceiling - 1, total);
}
Main Function
function sumSquareDifference(n) {
// total for sum of squares of the n natural numbers
let sumOfSquares = getSumSquares(n);
// total of square of the sum
let squareOfSum = getSquareSum(n);
// get difference between the two
return squareOfSum - sumOfSquares;
}
Altogether now
function getSumSquares(ceiling, total = 0) {
if (ceiling === 0) {
return total;
}
total += ceiling ** 2;
return getSumSquares(ceiling - 1, total);
}
function getSquareSum(ceiling, total = 0) {
if (ceiling === 0) {
return total ** 2;
}
total += ceiling;
return getSquareSum(ceiling - 1, total);
}
function sumSquareDifference(n) {
// total for sum of squares of the n natural numbers
let sumOfSquares = getSumSquares(n);
// total of square of the sum
let squareOfSum = getSquareSum(n);
// get difference between the two
return squareOfSum - sumOfSquares;
}
let tenSum = sumSquareDifference(10);
let hundoSum = sumSquareDifference(100);
Final Thoughts
Using those two methods, recursion, and functional programming, we have a nicely composed solution that is highly legible.
Like all things, this can be improved. If you have recommendations or improvements, throw down a comment and let me know!
As always, happy coding!
Plugs
Book
I'm writing a book about graphic design and how it relates to software development! If you're interested, sign up here for updates.
Music
I also write music! Check it out here:
https://open.spotify.com/artist/1o6CGTMPjk1C0IdK9jV2H1
https://www.youtube.com/channel/UCqxQspCPTcE_wH0KBE5J-aw
https://music.apple.com/us/artist/modulo/1499420471
Support
If you like this article and want to see more, the best way to do that is to subscribe/follow me on here! If you are feeling gracious, you can buy me a coffee!
Resources
This video is more specific to the event loop, but it covers what happens when the call stack is exceeded around the 7:00 mark.
Top comments (4)
In Rust it is pretty simple using ranges and
Iterator
s -Playground
You say simple, but that looks really complicated to me haha
Thanks for sharing! I'm always interested in what the solutions look like in other languages 👍🏽
I mean, JavaScript has similar constructs:
This could be further simplified with generator functions to get the iterator behavior seen in the Rust example.
Yep, that is definitely one way to do it. I personally prefer more legible code (because I'm a simple human), but this gets the job done.
Thanks for sharing!