Fibonacci Number

Problem Statement

Constraints

Solution 1: Recursive Approach

function fibonacciRecursive(n) { // Basic Recursive Approach with Input Validation
    if (typeof n === 'string') {
        n = parseInt(n, 10); // Convert string to integer
    }

    if (isNaN(n) || n < 0) {
        throw new Error("Input must be a non-negative integer");
    }

    if (n <= 1) return n; // Base cases: F(0) = 0 and F(1) = 1

    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
} 

const n1 = 2;
fibonacciRecursive(n1);  //output: 1 

const n2 = 3;
fibonacciRecursive(n2);  //output: 2 

const n3 = 4;
fibonacciRecursive(n3);  //output: 3 

Solution 2: Memoization (Top-Down Dynamic Programming)

function fibonacciMemoized(n, memo = {}) { // Recursive with Memoization
    if (n in memo) return memo[n];
    if (n <= 1) return n;
    memo[n] = fibonacciMemoized(n - 1, memo) + fibonacciMemoized(n - 2, memo);
    return memo[n];
} 

const n1 = 2;
fibonacciMemoized(n1);  //output: 1 

const n2 = 3;
fibonacciMemoized(n2);  //output: 2 

const n3 = 4;
fibonacciMemoized(n3);  //output: 3 

Solution 3: Iterative Approach

function fibonacciIterative(n) { // Iterative Approach
    if (n <= 1) return n;
    let previous = 0, current = 1;
    for (let i = 2; i <= n; i++) {
        const next = previous + current;
        previous = current;
        current = next;
    }
    return current;
} 

const n1 = 2;
fibonacciIterative(n1);  //output: 1 

const n2 = 3;
fibonacciIterative(n2);  //output: 2 

const n3 = 4;
fibonacciIterative(n3);  //output: 3 

Solution 4: Space-Optimized Iterative Approach

function fibonacciOptimized(n) { // Space-Optimized Iterative Approach
    if (n < 0) {
        throw new Error("Input must be a non-negative integer");
    }
    if (n <= 1) return n; // Base cases: F(0) = 0 and F(1) = 1

    let previous = 0; // F(0)
    let current = 1;  // F(1)

    for (let i = 2; i <= n; i++) {
        let next = previous + current; // Compute the next Fibonacci number
        previous = current; // Move the previous number to the current position
        current = next; // Update current to the next Fibonacci number
    }

    return current; // Return the nth Fibonacci number
} 

const n1 = 2;
fibonacciOptimized(n1);  //output: 1 

const n2 = 3;
fibonacciOptimized(n2);  //output: 2 

const n3 = 4;
fibonacciOptimized(n3);  //output: 3 

Solution 5: Binets Formula

function fibonacciBinet(n) {
    const sqrt5 = Math.sqrt(5);
    const phi = (1 + sqrt5) / 2;
    const psi = (1 - sqrt5) / 2;
    return Math.round((Math.pow(phi, n) - Math.pow(psi, n)) / sqrt5);
} 

const n1 = 2;
fibonacciBinet(n1);  //output: 1 

const n2 = 3;
fibonacciBinet(n2);  //output: 2 

const n3 = 4;
fibonacciBinet(n3);  //output: 3 

Solution 6: Using Recurrence Relation with Direct Computation

function fibonacciDirect(n) {
    if (n < 0) throw new Error("Input must be a non-negative integer");
    let a = 0, b = 1;
    while (n > 0) {
        let temp = a;
        a = b;
        b = temp + b;
        n--;
    }
    return a;
} 

const n1 = 2;
fibonacciDirect(n1);  //output: 1 

const n2 = 3;
fibonacciDirect(n2);  //output: 2 

const n3 = 4;
fibonacciDirect(n3);  //output: 3 

Solution 7: Using Generating Functions

function fibonacciGeneratingFunction(n) {
    if (n < 0) throw new Error("Input must be a non-negative integer");
    if (n === 0) return 0;
    if (n === 1) return 1;

    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        let c = a + b;
        a = b;
        b = c;
    }
    return b;
} 

const n1 = 2;
fibonacciGeneratingFunction(n1);  //output: 1 

const n2 = 3;
fibonacciGeneratingFunction(n2);  //output: 2 

const n3 = 4;
fibonacciGeneratingFunction(n3);  //output: 3 

Solution 8: Using Python-like List Comprehension in JavaScript

function fibonacciListComprehension(n) {
    if (n < 0) throw new Error("Input must be a non-negative integer");
    let fibs = [0, 1];
    [...Array(n - 1).keys()].forEach(() => fibs.push(fibs[fibs.length - 1] + fibs[fibs.length - 2]));
    return fibs[n];
} 

const n1 = 2;
fibonacciListComprehension(n1);  //output: 1 

const n2 = 3;
fibonacciListComprehension(n2);  //output: 2 

const n3 = 4;
fibonacciListComprehension(n3);  //output: 3 

Solution 9: Matrix Multiplication

function fibonacciMatrix(n) {
    if (n <= 1) return n;
    const matrix = [1, 1, 1, 0];
    const result = matrixPower(matrix, n - 1);
    return result[0]; // F(n) is at the top left corner of the result matrix
}


function matrixMultiply(a, b) {
    return [
        a[0] * b[0] + a[1] * b[2], // First row, first column
        a[0] * b[1] + a[1] * b[3], // First row, second column
        a[2] * b[0] + a[3] * b[2], // Second row, first column
        a[2] * b[1] + a[3] * b[3]  // Second row, second column
    ];
}

function matrixPower(matrix, n) {
    let result = [1, 0, 0, 1]; // Identity matrix
    let base = matrix;

    while (n > 0) {
        if (n % 2 === 1) {
            result = matrixMultiply(result, base);
        }
        base = matrixMultiply(base, base);
        n = Math.floor(n / 2);
    }

    return result;
} 

const n1 = 2;
fibonacciMatrix(n1);  //output: 1 

const n2 = 3;
fibonacciMatrix(n2);  //output: 2 

const n3 = 4;
fibonacciMatrix(n3);  //output: 3 

More Problems Solutions