I vividly remember the first time I encountered the nth Fibonacci algorithm. I had messaged a friend about starting to practice algorithms to which she responded:
Yeah! I just did one on the Fibonacci Sequence today! So fun!
I was immediately filled with flashbacks of my Masters program, sitting in a 500-level Music Theory course, checking for the Fibonacci sequence and the Golden Ratio in Sonatas by Mozart and Schubert.
Luckily for all of us, this algorithm problem's solution isn't as complicated as music theory at 8am. This time, it's the computer's job to figure out the sequence, we're just going to tell it how.
If you'd like to try the problem yourself first, you can find it here:
The Problem
The Fibonacci Number algorithm problem is as follows:
The Fibonacci sequence is derived of numbers where each number is the sum of the preceding numbers in the sequence. The sequence begins with 0 and 1.
Write a function that takes a integer,n
, which represents an index in the sequence and return the Fibonacci Number held at that position.
Example
Fibonacci Sequence:
0, 1, 1, 2, 3, 5, 8, 13...
n
=4
output =3
The Approach
We need a way to construct the Fibonacci sequence programmatically but we only need to construct it up to the n
th position, and then return the number we find there.
It might be tempting to try this problem using recursion, where you call your function from within itself until you've reached the result:
//a recursive solution
function nthFib(n) {
if (n <= 1)
return n;
return nthFib(n-1) + nthFib(n-2);
}
However, this approach solves for the same number in the sequence multiple times, which problematic from an optimization standpoint, and that's the whole reason that you're here, is it not?
You could clean this up a bit by using memoization (storing the results from a function call to prevent recalculating the same results again), but it's still going to run up space complexity (the amount of memory an algorithm takes up) with the memoization, which is wasteful, since we don't care about retaining the entire sequence in our output.
Instead, let's think about how you might solve this problem with your regular, human brain, not the computer. I'm thinking it would go like this:
- Start with
0
and1
. - Sum the next number in the sequence by adding your previous two numbers:
0 + 1 = 1
- Sum the second-to-last of your previous numbers with your new number:
1 + 1 = 2
- Repeat steps 2-3 until you get to the
n
th position of the sequence. - Tell me the answer you got.
Let's try that instead.
Variables Used:
-
prevTwo
- an array that holds the previous two numbers of the sequence -
i
- a counter variable in ourfor
loop -
sum
- the sum ofprevTwo[0]
andprevTwo[1]
in the loop
Line-by-Line Walkthrough:
function nthFib(n) {...}
-
Initialize the variable
prevTwo
with a value of[0,1]
, representing the start of the sequenceshow
let prevTwo = [0, 1];
-
Create a
for
loop which will iterate until we've reached then
th number in the sequence, initialize variablei
with value of0
.show
for (let i = 0; i <= n; i++) {...
-
Inside of the loop, initialize a variable
sum
that is equal toprevTwo[0]
+prevTwo[1]
.show
let sum = prevTwo[0] + prevTwo[1];
-
Still inside the loop, set the values held in
prevTwo
to be our new previous two numbers in the sequence, the number held atprevTwo[1]
and our newsum
.show
prevTwo = [prevTwo[1], sum]; }
-
When the loop is finished, return
prevTwo[1]
. This is ourn
th Fibonacci Numbershow
return prevTwo[1] }
Show Me The Logs
Here are my console.logs for this problem.
For the best experience, view them on replit, where you can fork it and feed your own string into the function!
๐ ๐ ๐ Nth FIBONACCI NUMBER STARTING NOW ๐ ๐ ๐
๐ฅ n = 5
================= FOR LOOP: 1 OF 4 =================
Fibonacci Sequence, so far: [ 0, 1 ]
๐ธ prevTwo = [ 0, 1 ]
๐ธ i = 0
๐งฎ ...calculating sum... ๐งฎ
๐ธ sum = 0 + 1 = 1
โ Moving 1 position [0]
โ Moving 1 into position [1]
prevTwo is now [ 1 , 1 ]
================= FOR LOOP: 2 OF 4 =================
Fibonacci Sequence, so far: [ 0, 1, 1 ]
๐ธ prevTwo = [ 1, 1 ]
๐ธ i = 1
๐งฎ ...calculating sum... ๐งฎ
๐ธ sum = 1 + 1 = 2
โ Moving 1 position [0]
โ Moving 2 into position [1]
prevTwo is now [ 1 , 2 ]
================= FOR LOOP: 3 OF 4 =================
Fibonacci Sequence, so far: [ 0, 1, 1, 2 ]
๐ธ prevTwo = [ 1, 2 ]
๐ธ i = 2
๐งฎ ...calculating sum... ๐งฎ
๐ธ sum = 1 + 2 = 3
โ Moving 2 position [0]
โ Moving 3 into position [1]
prevTwo is now [ 2 , 3 ]
================= FOR LOOP: 4 OF 4 =================
Fibonacci Sequence, so far: [ 0, 1, 1, 2, 3 ]
๐ธ prevTwo = [ 2, 3 ]
๐ธ i = 3
๐งฎ ...calculating sum... ๐งฎ
๐ธ sum = 2 + 3 = 5
โ Moving 3 position [0]
โ Moving 5 into position [1]
prevTwo is now [ 3 , 5 ]
=============== ๐ Finished Looping ๐ ===============
๐ ๐ ๐ Final Solution ๐ ๐ ๐
The 5 th number in the Fibinacci Sequence is 5 !
Solution
Finally, if you'd like to see a clean, log-free version of the solution, here it is:
View Solution
function nthFib(n) {
let prevTwo = [0, 1];
for (let i = 0; i < n - 1; i++) {
let sum = prevTwo[0] + prevTwo[1];
prevTwo = [prevTwo[1], sum];
}
return prevTwo[1]
}
Thanks for reading and I wish you luck on whatever algorithmic endeavor brought you to this post. โฅ
Top comments (0)