Generate Fibonacci Sequence - Practice Coding Problems

Generate Fibonacci Sequence - Problem

JavaScript Easy

Write a generator function that returns a generator object which yields the Fibonacci sequence.

The Fibonacci sequence is defined by the relation Xn = Xn-1 + Xn-2.

The first few numbers of the series are: 0, 1, 1, 2, 3, 5, 8, 13...

Your generator should yield numbers indefinitely when called repeatedly.

Input & Output

Example 1 — First 6 Numbers

$ Input: n = 6

› Output: [0,1,1,2,3,5]

💡 Note: The first 6 Fibonacci numbers: F(0)=0, F(1)=1, F(2)=0+1=1, F(3)=1+1=2, F(4)=1+2=3, F(5)=2+3=5

Example 2 — First 8 Numbers

$ Input: n = 8

› Output: [0,1,1,2,3,5,8,13]

💡 Note: Extending further: F(6)=3+5=8, F(7)=5+8=13. Each number is sum of previous two.

Example 3 — Edge Case

$ Input: n = 1

› Output: [0]

💡 Note: Only the first Fibonacci number, which is 0 by definition.

Constraints

1 ≤ n ≤ 50
Generated numbers will fit in 64-bit integer

Visualization

Tap to expand

Understanding the Visualization

Input

Number n indicating how many Fibonacci numbers to generate

Process

Use relation F(n) = F(n-1) + F(n-2) with F(0)=0, F(1)=1

Output

Array containing first n Fibonacci numbers

Key Takeaway

🎯 Key Insight: Only the previous two numbers are needed to generate the next Fibonacci number

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is that each Fibonacci number only depends on the previous two numbers. The optimal approach uses an iterative generator that maintains only two variables, achieving O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Generator	O(n)	O(n)	Use memoization to cache previously calculated Fibonacci numbers
Iterative Generator	O(n)	O(1)	Generate Fibonacci numbers iteratively keeping track of last two values
Recursive Generator	O(2^n)	O(n)	Use recursive function to calculate each Fibonacci number

Memoized Generator — Algorithm Steps

Create a cache/memo dictionary
Check cache before calculating
If not in cache, calculate recursively
Store result in cache and return

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Cache

Look for previously calculated value

Calculate & Store

If not found, calculate and store in cache

Reuse

Future requests return cached value instantly

Code -

solution.c — C

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

#define MAX_N 100
static long long memo[MAX_N];
static int memo_initialized[MAX_N];

long long fibMemo(int k) {
    if (memo_initialized[k]) return memo[k];
    if (k <= 1) {
        memo[k] = k;
        memo_initialized[k] = 1;
        return k;
    }
    memo[k] = fibMemo(k-1) + fibMemo(k-2);
    memo_initialized[k] = 1;
    return memo[k];
}

void solution(int n, long long* result) {
    memset(memo_initialized, 0, sizeof(memo_initialized));
    for (int i = 0; i < n; i++) {
        result[i] = fibMemo(i);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    
    long long* result = (long long*)malloc(n * sizeof(long long));
    solution(n, result);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%lld", result[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each Fibonacci number is calculated exactly once and cached

✓ Linear Growth

Space Complexity

O(n)

Cache stores all calculated Fibonacci numbers plus recursion stack

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 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

Memoized Generator — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler