JavaScript Program for Nth Catlan Numbers

JavaScript Program for Armstrong Numbers

Catalan numbers are defined as a mathematical sequence that consists of positive integers, which can be used to find the number of possibilities of various combinations.

The nth term in the sequence denoted C_n, is found in the following formula:

The first few Catalan numbers for n = 0, 1, 2, 3, … are : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

Below are the approaches forNth Catlan numbers in JavaScript:

Table of Content

Using Recursive approach
Using Dynamic programming
Using Binomial Coefficients

Using Recursive approach

In this approach, we use a recursive function to calculate the nth Catalan number. The function iterates through all possible values of i, from 0 to n-1, to calculate the Catalan number for both i and n-i-1. We then multiply these results together and add them to the total sum.

The recursive formula for Catalan numbers is:

Example: Implementation for nth Catlan numbers using recursive approach.

JavaScript

function catalanRecursive(n) {
    if (n <= 1) {
        return 1;
    }
    let res = 0;
    for (let i = 0; i < n; i++) {
        res += catalanRecursive(i) * catalanRecursive(n - i - 1);
    }
    return res;
}

const n = 5;
console.log(`The ${n}th Catalan number is: ${catalanRecursive(n)}`);

Output

The 5th Catalan number is: 42

Time Complexity: O(4ⁿ)

Space Complexity: O(n)

Using Dynamic programming

Using dynamic programming for Catalan numbers involves building up the sequence from the base cases (C0 = C1 = 1) using a bottom-up approach. We store intermediate results in an array to avoid redundant calculations. Starting with the base cases, we compute each subsequent Catalan number until we reach the desired nth Catalan number. This approach optimizes computation by reusing previously calculated values, resulting in an efficient solution for calculating Catalan numbers.

Approach:

Create an array catalan to store Catalan numbers, initializing the first two values as 1 (base cases).
Use nested loops to fill the array with Catalan numbers, starting from index 2 up to the desired nth Catalan number.
Calculate each Catalan number by summing up products of previously computed Catalan numbers, avoiding redundant calculations.
Utilize an array to store intermediate results, optimizing memory usage and avoiding recursive function calls.
Return the nth Catalan number computed using dynamic programming for the given input n.

Example: Demonstration for nth Catlan numbers using Dynamic programming.

JavaScript

function catalanDynamic(n) {
    let catalan = new Array(n + 1).fill(0);
    catalan[0] = 1;
    catalan[1] = 1;
    for (let i = 2; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            catalan[i] += catalan[j] * catalan[i - j - 1];
        }
    }
    return catalan[n];
}

// Example
const n = 6;
console.log(`The ${n}th Catalan number is: ${catalanDynamic(n)}`);

Output

The 6th Catalan number is: 132

Time complexity: O(n^2)

Space complexity: O(n)

Using Binomial Coefficients

Another efficient approach to calculate Catalan numbers is by using the formula involving binomial coefficients: We can also use the below formula to find nth Catalan number in O(n) time.

Example: Implementation for nth Catlan numbers using recursive approach.

JavaScript

function binomialCoeff(n, k) {
    let res = 1;
    if (k > n - k) k = n - k;
    for (let i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

function catalanBinomial(n) {
    let x = binomialCoeff(2 * n, n) / (n + 1);
    console.log(x);
}

catalanBinomial(5);

Output

Time Complexity: O(n)

Space Complexity:O(1)

Tags:

#JavaScript Programs #JavaScript #Web Technologies

JavaScript Program for Armstrong Numbers

JavaScript Program for Nth Catlan Numbers

Using Recursive approach

Using Dynamic programming

Approach:

Using Binomial Coefficients

Contact Us