Back
Close

Fibonacci

cehsu
1,035 views

Fibonacci

The first two numbers in the Fibonacci sequence are 1 and 1. Every additional number in the sequence is the sum of the two previous numbers. The first six numbers of the Fibonacci sequence are 1, 1, 2, 3, 5 and 8.

Source:https://www.freecodecamp.com/challenges/sum-all-odd-fibonacci-numbers

Check for the fibonacci number

Write a getFib function that takes a number n as a parameter and returns the nth Fibonacci number. If n is zero, zero should be returned.

Sample Input and Output

Input: 4 Output: 3

Optimization

Try solving the problem using memoization and tabulation.

See:

https://www.rithmschool.com/courses/javascript-computer-science-fundamentals/dynamic-programming,

https://indrabasak.wordpress.com/2016/04/03/exploring-fibonacci/

How much faster was the problem solved? How can you account for this in terms of time complexity? How about matrix exponentiation and fast doubling?

See:

https://www.nayuki.io/page/fast-fibonacci-algorithms

Write the getFib function
function getFib (fibIndex) {
// Your code here:
}
module.exports = getFib;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants