Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
The Fibonacci numbers 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).
Input:
- An integer n (0 ≤ n ≤ 30)
Output:
- The nth Fibonacci number
Constraints:
- 0 ≤ n ≤ 30
Examples:
Example 1:
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1
Example 2:
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2
Example 3:
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3
Example 4:
Input: n = 0
Output: 0
Explanation: F(0) = 0 by definition
Solutions
Approach 1: Recursive Solution (Naive)
The most straightforward approach using the mathematical definition, but has exponential time complexity.
Algorithm:
- Base cases: if n ≤ 1, return n
- Recursively calculate F(n-1) + F(n-2)
Python:
def fib_recursive(n):
"""
Naive recursive solution
Time: O(2^N) - exponential due to repeated calculations
Space: O(N) - recursion call stack
"""
if n <= 1:
return n
return fib_recursive(n - 1) + fib_recursive(n - 2)
# Example usage
print(fib_recursive(5)) # Output: 5
Java:
class Solution {
/**
* Naive recursive solution
* Time: O(2^N)
* Space: O(N)
*/
public int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
}
Go:
// fibRecursive - Naive recursive solution
// Time: O(2^N)
// Space: O(N)
func fibRecursive(n int) int {
if n <= 1 {
return n
}
return fibRecursive(n-1) + fibRecursive(n-2)
}
JavaScript:
/**
* Naive recursive solution
* Time: O(2^N)
* Space: O(N)
*/
function fibRecursive(n) {
if (n <= 1) {
return n;
}
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
C#:
public class Solution {
/// <summary>
/// Naive recursive solution
/// Time: O(2^N)
/// Space: O(N)
/// </summary>
public int Fib(int n) {
if (n <= 1) {
return n;
}
return Fib(n - 1) + Fib(n - 2);
}
}
Approach 2: Memoization (Top-Down DP)
Optimize the recursive solution by caching previously computed results.
Algorithm:
- Use a cache (dictionary/map) to store computed values
- Before computing, check if value exists in cache
- If exists, return cached value; otherwise compute and cache
Python:
def fib_memoization(n, memo=None):
"""
Top-down DP with memoization
Time: O(N) - each subproblem computed once
Space: O(N) - memoization table + recursion stack
"""
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memoization(n - 1, memo) + fib_memoization(n - 2, memo)
return memo[n]
def fib_memoization_decorator(n):
"""
Using functools.lru_cache decorator
Time: O(N)
Space: O(N)
"""
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
return fib(n)
# Example usage
print(fib_memoization(10)) # Output: 55
Java:
import java.util.HashMap;
import java.util.Map;
class Solution {
private Map<Integer, Integer> memo = new HashMap<>();
/**
* Top-down DP with memoization
* Time: O(N)
* Space: O(N)
*/
public int fib(int n) {
if (memo.containsKey(n)) {
return memo.get(n);
}
if (n <= 1) {
return n;
}
int result = fib(n - 1) + fib(n - 2);
memo.put(n, result);
return result;
}
/**
* Alternative implementation with explicit memo parameter
* Time: O(N)
* Space: O(N)
*/
public int fibWithMemo(int n) {
Map<Integer, Integer> memo = new HashMap<>();
return fibHelper(n, memo);
}
private int fibHelper(int n, Map<Integer, Integer> memo) {
if (memo.containsKey(n)) {
return memo.get(n);
}
if (n <= 1) {
return n;
}
int result = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
memo.put(n, result);
return result;
}
}
Go:
// fibMemoization - Top-down DP with memoization
// Time: O(N)
// Space: O(N)
func fibMemoization(n int) int {
memo := make(map[int]int)
return fibMemoHelper(n, memo)
}
func fibMemoHelper(n int, memo map[int]int) int {
if val, exists := memo[n]; exists {
return val
}
if n <= 1 {
return n
}
result := fibMemoHelper(n-1, memo) + fibMemoHelper(n-2, memo)
memo[n] = result
return result
}
JavaScript:
/**
* Top-down DP with memoization
* Time: O(N)
* Space: O(N)
*/
function fibMemoization(n, memo = {}) {
if (n in memo) {
return memo[n];
}
if (n <= 1) {
return n;
}
memo[n] = fibMemoization(n - 1, memo) + fibMemoization(n - 2, memo);
return memo[n];
}
/**
* Using Map for memoization
* Time: O(N)
* Space: O(N)
*/
function fibMemoizationMap(n) {
const memo = new Map();
function fib(n) {
if (memo.has(n)) {
return memo.get(n);
}
if (n <= 1) {
return n;
}
const result = fib(n - 1) + fib(n - 2);
memo.set(n, result);
return result;
}
return fib(n);
}
C#:
using System.Collections.Generic;
public class Solution {
private Dictionary<int, int> memo = new Dictionary<int, int>();
/// <summary>
/// Top-down DP with memoization
/// Time: O(N)
/// Space: O(N)
/// </summary>
public int Fib(int n) {
if (memo.ContainsKey(n)) {
return memo[n];
}
if (n <= 1) {
return n;
}
int result = Fib(n - 1) + Fib(n - 2);
memo[n] = result;
return result;
}
/// <summary>
/// Alternative implementation with explicit memo parameter
/// Time: O(N)
/// Space: O(N)
/// </summary>
public int FibWithMemo(int n) {
Dictionary<int, int> memo = new Dictionary<int, int>();
return FibHelper(n, memo);
}
private int FibHelper(int n, Dictionary<int, int> memo) {
if (memo.ContainsKey(n)) {
return memo[n];
}
if (n <= 1) {
return n;
}
int result = FibHelper(n - 1, memo) + FibHelper(n - 2, memo);
memo[n] = result;
return result;
}
}
Approach 3: Tabulation (Bottom-Up DP)
Build the solution iteratively from the bottom up using a table to store results.
Algorithm:
- Create a table to store Fibonacci numbers
- Initialize base cases: F(0) = 0, F(1) = 1
- Fill the table iteratively: F(i) = F(i-1) + F(i-2)
Python:
def fib_tabulation(n):
"""
Bottom-up DP with tabulation
Time: O(N) - single pass through numbers
Space: O(N) - DP table
"""
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Example usage
print(fib_tabulation(10)) # Output: 55
Java:
class Solution {
/**
* Bottom-up DP with tabulation
* Time: O(N)
* Space: O(N)
*/
public int fib(int n) {
if (n <= 1) {
return n;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
Go:
// fibTabulation - Bottom-up DP with tabulation
// Time: O(N)
// Space: O(N)
func fibTabulation(n int) int {
if n <= 1 {
return n
}
dp := make([]int, n+1)
dp[0] = 0
dp[1] = 1
for i := 2; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
JavaScript:
/**
* Bottom-up DP with tabulation
* Time: O(N)
* Space: O(N)
*/
function fibTabulation(n) {
if (n <= 1) {
return n;
}
const dp = new Array(n + 1);
dp[0] = 0;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
C#:
public class Solution {
/// <summary>
/// Bottom-up DP with tabulation
/// Time: O(N)
/// Space: O(N)
/// </summary>
public int Fib(int n) {
if (n <= 1) {
return n;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
Approach 4: Space Optimized DP
Since we only need the last two values, we can optimize space to O(1).
Algorithm:
- Keep track of only the last two Fibonacci numbers
- Update them iteratively without storing the entire sequence
Python:
def fib_optimized(n):
"""
Space-optimized DP solution
Time: O(N) - single pass
Space: O(1) - only storing two variables
"""
if n <= 1:
return n
prev2 = 0 # F(0)
prev1 = 1 # F(1)
for i in range(2, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
def fib_optimized_pythonic(n):
"""
Pythonic space-optimized solution using tuple unpacking
Time: O(N)
Space: O(1)
"""
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
# Example usage
print(fib_optimized(10)) # Output: 55
Java:
class Solution {
/**
* Space-optimized DP solution
* Time: O(N)
* Space: O(1)
*/
public int fib(int n) {
if (n <= 1) {
return n;
}
int prev2 = 0; // F(0)
int prev1 = 1; // F(1)
for (int i = 2; i <= n; i++) {
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
Go:
// fibOptimized - Space-optimized DP solution
// Time: O(N)
// Space: O(1)
func fibOptimized(n int) int {
if n <= 1 {
return n
}
prev2, prev1 := 0, 1 // F(0), F(1)
for i := 2; i <= n; i++ {
current := prev1 + prev2
prev2 = prev1
prev1 = current
}
return prev1
}
// Alternative with multiple assignment
func fibOptimizedAlt(n int) int {
if n <= 1 {
return n
}
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a+b
}
return b
}
JavaScript:
/**
* Space-optimized DP solution
* Time: O(N)
* Space: O(1)
*/
function fibOptimized(n) {
if (n <= 1) {
return n;
}
let prev2 = 0; // F(0)
let prev1 = 1; // F(1)
for (let i = 2; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
/**
* Using destructuring assignment
* Time: O(N)
* Space: O(1)
*/
function fibOptimizedDestructuring(n) {
if (n <= 1) {
return n;
}
let [a, b] = [0, 1];
for (let i = 2; i <= n; i++) {
[a, b] = [b, a + b];
}
return b;
}
C#:
public class Solution {
/// <summary>
/// Space-optimized DP solution
/// Time: O(N)
/// Space: O(1)
/// </summary>
public int Fib(int n) {
if (n <= 1) {
return n;
}
int prev2 = 0; // F(0)
int prev1 = 1; // F(1)
for (int i = 2; i <= n; i++) {
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
/// <summary>
/// Using tuple for swapping
/// Time: O(N)
/// Space: O(1)
/// </summary>
public int FibTuple(int n) {
if (n <= 1) {
return n;
}
(int a, int b) = (0, 1);
for (int i = 2; i <= n; i++) {
(a, b) = (b, a + b);
}
return b;
}
}
Approach 5: Matrix Exponentiation
Use matrix multiplication to compute Fibonacci in O(log N) time.
Python:
def fib_matrix(n):
"""
Matrix exponentiation approach
Time: O(log N) - due to fast exponentiation
Space: O(log N) - recursion depth for exponentiation
"""
if n <= 1:
return n
def matrix_multiply(A, B):
"""Multiply two 2x2 matrices"""
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 matrix_power(matrix, power):
"""Compute matrix^power using fast exponentiation"""
if power == 1:
return matrix
if power % 2 == 0:
half = matrix_power(matrix, power // 2)
return matrix_multiply(half, half)
else:
return matrix_multiply(matrix, matrix_power(matrix, power - 1))
# Base matrix [[1, 1], [1, 0]]
base_matrix = [[1, 1], [1, 0]]
result_matrix = matrix_power(base_matrix, n)
return result_matrix[0][1]
Key Insights
- Optimal Substructure: F(n) depends on solutions to smaller subproblems F(n-1) and F(n-2)
- Overlapping Subproblems: Naive recursion recomputes the same values multiple times
- Memoization vs Tabulation: Top-down vs bottom-up approaches both achieve O(N) time
- Space Optimization: Only need last two values, reducing space from O(N) to O(1)
- Different Complexities: Various approaches offer different time-space tradeoffs
Edge Cases
- n = 0: Return 0 by definition
- n = 1: Return 1 by definition
- Large n: Consider integer overflow for very large Fibonacci numbers
- Negative n: Problem constraints typically specify n ≥ 0
Test Cases
def test_fibonacci():
test_cases = [
(0, 0),
(1, 1),
(2, 1),
(3, 2),
(4, 3),
(5, 5),
(6, 8),
(10, 55)
]
for n, expected in test_cases:
assert fib_optimized(n) == expected
print(f"F({n}) = {expected} ✓")
test_fibonacci()
Common Mistakes
- Off-by-one errors: Incorrect base cases or loop bounds
- Not handling edge cases: Forgetting n = 0 or n = 1 cases
- Integer overflow: Not considering large numbers in production code
- Inefficient recursion: Using naive recursion without memoization
- Wrong initialization: Incorrect initial values in iterative solutions
Follow-up Questions
- Fibonacci variants: What if the sequence started with different base cases?
- Modular arithmetic: Compute F(n) mod M for large numbers
- Nth Fibonacci digit: Find specific digits of very large Fibonacci numbers
- Fibonacci search: Use Fibonacci numbers in search algorithms
- Golden ratio: Relationship between Fibonacci sequence and golden ratio
- Matrix approach: Extend to compute F(n) in O(log N) time
- Memory optimization: How to handle very large n with limited memory?
Interview Tips
- Start simple: Begin with recursive solution, then optimize
- Discuss tradeoffs: Compare time/space complexity of different approaches
- Code incrementally: Implement memoization, then tabulation, then space optimization
- Consider constraints: Ask about the range of n and integer overflow
- Test thoroughly: Verify edge cases and small examples
- Explain intuition: Describe why DP works for this problem