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

Solution: Fibonacci Number

Explore how to efficiently calculate the Fibonacci number for a given integer using a mathematical approach based on the golden ratio. Understand the use of Binet’s formula to achieve a logarithmic time solution with constant space, avoiding traditional slow recursive methods. This lesson guides you through the implementation and reasoning behind this optimized method.

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 ...