Fibonacci Number

Difficulty: Easy | Acceptance: 74.10% | Paid: No Topics: Math, Dynamic Programming, Recursion, Memoization

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

• Examples
• Constraints
• Approach 1: Recursion (Brute Force)
• Approach 2: Recursion with Memoization (Top-Down DP)
• Approach 3: Dynamic Programming (Bottom-Up)
• Approach 4: Space Optimized DP
• Approach 5: Matrix Exponentiation
• Approach 6: Binet’s Formula (Math)

Examples

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints

0 <= n <= 30

Approach 1: Recursion (Brute Force)

Intuition Directly implement the mathematical definition of the Fibonacci sequence using recursion. This is the most intuitive but least efficient method.

Steps

• Handle base cases: if n is 0 return 0, if n is 1 return 1.
• For n > 1, recursively call fib(n-1) and fib(n-2) and return their sum.

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        return self.fib(n - 1) + self.fib(n - 2)

Complexity

• Time: O(2ⁿ) - Each call branches into two more calls.
• Space: O(n) - Depth of the recursion stack.
• Notes: Highly inefficient due to repeated calculations of the same subproblems.

Approach 2: Recursion with Memoization (Top-Down DP)

Intuition Store the results of subproblems in a hash map or array to avoid redundant calculations. This is known as Top-Down Dynamic Programming.

Steps

• Create a memoization storage (array or dictionary).
• In the recursive function, check if the result for n is already in the memo.
• If yes, return it. If no, calculate it recursively, store it in memo, then return it.

class Solution:
    def fib(self, n: int) -> int:
        memo = {}
        def helper(n):
            if n in memo: return memo[n]
            if n <= 1: return n
            memo[n] = helper(n - 1) + helper(n - 2)
            return memo[n]
        return helper(n)

Complexity

• Time: O(n) - Each number from 0 to n is calculated exactly once.
• Space: O(n) - For memo array and recursion stack depth.
• Notes: Significantly faster than brute force recursion.

Approach 3: Dynamic Programming (Bottom-Up)

Intuition Build the solution iteratively from the base cases up to n, storing results in an array (DP table). This avoids recursion overhead.

Steps

• Initialize a dp array of size n + 1.
• Set base cases: dp[0] = 0, dp[1] = 1.
• Iterate from 2 to n, setting dp[i] = dp[i-1] + dp[i-2].
• Return dp[n].

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1: return n
        dp = [0] * (n + 1)
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

Complexity

• Time: O(n) - Single pass through the numbers.
• Space: O(n) - To store the dp array.
• Notes: Good balance of simplicity and efficiency.

Approach 4: Space Optimized DP

Intuition Since we only ever need the previous two numbers to calculate the current one, we don’t need to store the entire array.

Steps

• Handle base cases.
• Initialize two variables, prev (F(i-2)) and curr (F(i-1)).
• Iterate from 2 to n. In each step, calculate next = prev + curr, then update prev = curr, curr = next.
• Return curr.

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1: return n
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b

Complexity

• Time: O(n) - Single pass.
• Space: O(1) - Only two variables used.
• Notes: The most optimal solution for standard constraints.

Approach 5: Matrix Exponentiation

Intuition The Fibonacci sequence can be represented as a matrix transformation. Raising the transformation matrix to the power of n yields F(n).

Steps

• Represent the recurrence as [[1, 1], [1, 0]] * [F(n-1), F(n-2)]ᵀ = [F(n), F(n-1)]ᵀ.
• Use fast exponentiation (binary exponentiation) to compute the power of the matrix [[1, 1], [1, 0]]ⁿ⁻¹.
• The top-left element of the resulting matrix is F(n).

class Solution:
    def fib(self, n: int) -> int:
        if n == 0: return 0
        def multiply(A, B):
            return [
                [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
                [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
            ]
        def power(A, p):
            res = [[1, 0], [0, 1]]
            while p > 0:
                if p % 2 == 1:
                    res = multiply(res, A)
                A = multiply(A, A)
                p //= 2
            return res
        M = [[1, 1], [1, 0]]
        res = power(M, n - 1)
        return res[0][0]

Complexity

• Time: O(log n) - Due to fast exponentiation.
• Space: O(log n) - Recursion stack depth for the power function.
• Notes: Useful for very large n (e.g., n > 10⁹) where O(n) is too slow.

Approach 6: Binet’s Formula (Math)

Intuition There is a closed-form formula to calculate the nth Fibonacci number directly using the Golden Ratio.

Steps

• Calculate the Golden Ratio phi = (1 + sqrt(5)) / 2.
• Apply Binet’s formula: F(n) = round(phiⁿ / sqrt(5)).
• Return the result as an integer.

class Solution:
    def fib(self, n: int) -> int:
        phi = (1 + 5 ** 0.5) / 2
        return int(round((phi ** n - (1 - phi) ** n) / 5 ** 0.5))

Complexity

• Time: O(1) - Constant time arithmetic operations.
• Space: O(1) - No extra space used.
• Notes: While theoretically O(1), floating-point precision errors can occur for very large n, making it less reliable than integer arithmetic methods for exact results in competitive programming.