CoDEVIANT #26 — Fibonacci Fun

Our job is to find the nth Fibonacci number via a function we will write that takes an integer n. We will get the nth number by adding

So before I started this, I actually didn’t know what a Fibonacci Number was, honest to God.

I have a doctorate in music, I can help the patient onboard!

But to break it down really quickly, here’s what it is:

  • You always start with 0, followed by 1.

So now that we’ve got that out of the way…

Here’s my solution:

function getNthFib(n) {
let counter = 2
let array = [0, 1]
while(counter < n) {
array.push(array[array.length - 2] + array[array.length - 1])
counter++
}
return n === 1 ? 0 : n === 2 ? 1 : array[n-2] + array[n-3]
}

So first off, we can rely on 3 things in life:

  • Death

So that’s why we start our method by defining counter, which will have the value of 2, and array which will be an array containing the first two numbers in the Fibonacci Sequence

let counter = 2
let array = [0, 1]

Next we say that while counter is less than n, the integer that was passed as an argument into the method, we push a new number into the array. This number will be the second to the last number in the array and the last number in the array. Because arrays are zero-indexed, we use array.length — 2 for the second to last number and array.length — 1 for the last number. After that, we increment counter by one so that our while loop doesn’t go on forever.

while(counter < n) {
array.push(array[array.length - 2] + array[array.length - 1])
counter++
}

Finally, we say that if n was 1, we return 0. If n was 2, we return 1. This is because if we say that to get a Fibonacci Sequence number we have to add (lets say if we’re dealing with 2): the sum of the 2–2th number (which is 0) and the 2–1th number which is 1. If it’s 1, then we’re adding 0 and null. However, we follow that up by saying to return the sum of array[n-2] and array[n-3].

We use n-2 and n-3 due to the zero-indexed nature of arrays, so we aren’t off by one value in the array we built.

Pretty painless, huh?

Now what I’m really proud about is that the ‘best practices’ solution…is really very much the same. The only difference is that they don’t use an array to hold onto extra values that aren’t used, which honestly is much better.

function getNthFib(n) {
const lastTwo = [0,1]
let counter = 3
while(counter <= n) {
const nextFib = lastTwo[0] + lastTwo[1]
lastTwo[0] = lastTwo[1]
lastTwo[1] = nextFib
counter++
}
return n > 1 ? lastTwo[1] : lastTwo[0];
}

We see a lot of carried over ideas, like:

  • Starting an array with 0 and 1

The real difference is in the while-loop.

Bear in mind that counter was made 3 and that the while loop goes on as long as counter is less than or equal to n. This makes it so that we don’t have to switch up the array elements being returned at the end due to the zero-indexed nature of arrays.

Next it says that lastTwo[0], the first element of lastTwo, now equals the second element’s value. Then the value of the second element will be replaced with it’s own value plus the previous element, a variable that is created in the while-loop in each iteration: nextFib.

while(counter <= n) {
const nextFib = lastTwo[0] + lastTwo[1]
lastTwo[0] = lastTwo[1]
lastTwo[1] = nextFib
counter++
}

Finally, the solution finishes with a simple question:

If n is more than 1, return the second value in the array: lastTwo[1], otherwise return the first value: lastTwo[0].

Remember in the while-loop that lastTwo[1] is always eventually going to be that sum of the two values before it. So if our n is more than one, we’re definitely going to want to return that second element in lastTwo. This also works for our more diminutive instances of n, where its 1 or 0. Remember that the while-loop only works when n is more than or equal to counter. If n is 1 or 0, we skip the entire thing and return lastTwo[0]. *which will be zero*.

return n > 1 ? lastTwo[1] : lastTwo[0]

I feel really good about being able to solve this one without any help. I learned a new math concept and did a pretty good job. In most computer problems you want to save memory, so by avoiding building out a long array, the latter solution was better overall. Still, I’d say it was a good hustle.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store