Fibonacci Number - Practice Coding Problems

Fibonacci Number - Problem

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

Input & Output

Example 1 — Small Number

$ Input: n = 2

› Output: 1

💡 Note: F(2) = F(1) + F(0) = 1 + 0 = 1

Example 2 — Medium Number

$ Input: n = 3

› Output: 2

💡 Note: F(3) = F(2) + F(1) = 1 + 1 = 2

Example 3 — Base Case

$ Input: n = 4

› Output: 3

💡 Note: F(4) = F(3) + F(2) = 2 + 1 = 3

Constraints

0 ≤ n ≤ 30

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n (e.g., n = 4)

Build Sequence

F(n) = F(n-1) + F(n-2)

Output

Return F(n) = 3

Key Takeaway

🎯 Key Insight: Only need to track the last two values to compute the next Fibonacci number

Asked in

G Google 15 a Amazon 12 f Facebook 8 🍎 Apple 6

The key insight is that each Fibonacci number is just the sum of the previous two numbers. The optimal approach uses space-optimized DP with two variables to track the last two values. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive (Brute Force)	O(2ⁿ)	O(n)	Direct recursive implementation following the mathematical definition
Space-Optimized DP	O(n)	O(1)	Track only the last two values instead of entire array
Bottom-Up DP (Tabulation)	O(n)	O(n)	Build up from F(0) to F(n) using iterative approach
Memoization (Top-Down DP)	O(n)	O(n)	Cache recursive results to avoid redundant calculations

Recursive (Brute Force) — Algorithm Steps

Base cases: return 0 for n=0, return 1 for n=1
Recursive case: return F(n-1) + F(n-2)
Each call spawns two more recursive calls

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Call

F(4) splits into F(3) + F(2)

Recursive Expansion

Each call creates two more calls

Base Cases

F(0)=0 and F(1)=1 stop recursion

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int n) {
    if (n <= 1) {
        return n;
    }
    return solution(n - 1) + solution(n - 2);
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each call branches into two recursive calls, creating exponential growth

✓ Linear Growth

Space Complexity

O(n)

Maximum recursion depth is n, using call stack space

⚡ Linearithmic Space

172.8K Views

Medium Frequency

~15 min Avg. Time

4.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive (Brute Force) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler