Welcome to Round Two of Project Euler! This time we're heading into the land of state management and that guy you've probably heard about: Fibonacci! I'm excited, are you excited?
Video Version
If you like to watch rather than read, check out the video that accompanies this article. If not, keep reading!
Problem 2: Even Fibonacci Numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Problem Statement
By considering the terms in the Fibonacci sequence that do not exceed the nth term, find the sum of the even-valued terms.
Solution
Breakdown of the Problem
Fibonacci sequence
It's stated in the problem, however, let's discuss what a Fibonacci sequence is a little bit and why it's important.
The next number is found by adding up the two numbers before it.
When we do this, it creates an interesting spiral, which is found in myriad places in nature.
We could probably talk all day about Fibonacci, but let's get back to code.
Steps
- Generate Fibonacci sequence
- Add our first term(1) + our second term (2)
- Add product of our previous numbers to second term
- Check to see if the value is even, if so, add it to a total sum.
- Repeat, infinitely...
Naive Approach
function fiboEvenSum(n) {
// setup placeholders for our three values
let fibNumSum = 0; // product of our two numbers
let fibCurrent = 0; // current number
let fibNext = 1; // next number
for (let i = 1; i <= n; i++) {
// find next number
let fibTotal = fibCurrent + fibNext;
// set first number to second number
fibCurrent = fibNext;
// set second number to total
fibNext = fibTotal;
// make sure the value is even
if (fibTotal % 2 == 0) {
fibNumSum += fibTotal;
}
}
// You can do it!
return fibNumSum;
}
fiboEvenSum(10); //44
Modulo
I talked about what modulo is in my first article, but I need to clarify a couple things. When you evaluate a modulo expression, it gives you the remainder of the division of the two numbers. In the case of 15 % 4 , that will give us a remainder of 3 because:
- 4 goes into 15 3 times.
- 15 - 3 * 4 (12) = 3
Therefore, 15 % 4 = 3 or 15 / 4 = 3 remainder 3
I don't know if that explains it well enough...but, if it still doesn't make sense. Check out the video in the resources section below!
Algorithmic Approach
I'm not going to sit here and try and explain someone else's code. However, I found a pretty awesome way of solving this problem via CodeFay.
CodeFay
/
ProjectEuler100
Project Euler 100 Challenge
ProjectEuler100
I'm returning to FreeCodeCamp in 2020 to attempt the Project Euler 100 Challenge.
Will it be really as hard as Dark Souls? Probably, but I'm up for the challenge!
Solved Problems:
- Multiples of 3 and 5 - Jan 14, 2020
- Even Fibonacci Numbers - Jan 17, 2020
- Largest prime factor - Jan 18, 2020
- Largest palindrome product - Jan 26, 2020
- Smallest multiple - Jan 26, 2020
- Sum square difference - Jan 26, 2020
- 10001st prime number - Jan 28, 2020
- Largest product in a series - Jan 28, 2020
- Special Pythagorean triplet - Jan 28, 2020
- Summation of Primes - Jan 28, 2020
It's an elegant approach, as well as a faster one. When I tested it against my naive approach, it was generally about 20% faster. I suggest checking it out if you want to see some cool code!
Final Thoughts
This problem is fairly straight-forward. What I like about this problem is it gets us thinking about the "state" of our app. We define our three values at the top of our function, then manipulate them within the for loop. This reduces what we have to do after we get all the fibonacci values.
As always, I'm sure there is room for improvement. If you have recommendations, let me know!
Resources
https://www.youtube.com/watch?v=pNXwzIohx8c&feature=emb_title
Top comments (0)