Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Fibonacci Number

Explore how to calculate the Fibonacci number for a given integer using a constant space method based on the golden ratio and Binet's formula. Understand the inefficiencies of naive recursion and dynamic programming, and learn to implement a solution that runs in logarithmic time by leveraging mathematical properties.

We'll cover the following...

Statement

The Fibonacci sequence is a famous series of numbers in which each value is created by adding the two preceding numbers. The sequence begins with:

  • F(0)=0F(0) = 0

  • F(1)=1F(1) = 1

From that point on, every term is defined as:

  • F(n)=F(n−1)+F(n−2)F(n) = F(n - 1) + F(n - 2), for any nn greater than 11 ...