Nth Catalan Number  

Difficulty Level Medium
Frequently asked in Amazon
Dynamic Programming Math

In the Nth Catalan number problem, we have given an integer n. Find the first n Catalan numbers. Catalan numbers are a series of positive integers which is seen in many counting problems.

They are used to count –

  • BSTs (Binary search trees) with n keys.
  • Certain types of lattice paths.
  • Permutations

and many more such problems. The recursive formula for Catalan numbers is –

C0 = 0 and Cn+1 = Σ Ci Cn-i for n>=0 and n=>i>=0.

The first few numbers of Catalan number series – 1, 1, 2, 5, 14…… for n = 0, 1, 2, 3, 4…… respectively. 

Please click Like if you loved this article?

Example  

Input : n=2

Output : 1 1

Input : n=9

Output : 1 1 2 5 14 42 132 429 1430

Recursive Method for Nth catalon number  

Algorithm

  1. Initialise a variable n.
  2. Base case – if n is less than equal to 1 return 1.
  3. Recursive case – return sum of all cat (i) x cat (n-i-1) for all i between 0 and n (0 inclusive).

Time Complexity: O(3n)

Space Complexity: O(1)

Implementation for Nth catalon number

C++ Program

#include<bits/stdc++.h> 
using namespace std; 
  
long int cat(int n){ 
    // Base case 
    if(n<=1) 
        return 1; 
  
    // cat(n)= sum of cat(i)*cat(n-i-1) 
    long int r = 0; 
    for (int i=0; i<n; i++) 
        r += cat(i)*cat(n-i-1); 
    return r; 
} 
  
int main(){
    int n=3;
    for (int i=0; i<n; i++) 
        cout<<cat(i)<< " "; 
    return 0; 
}
1 1 2

Java Program

class Catalan{ 
    int cat(int n) { 
        int r = 0; 
          
        // Base case 
        if(n<=1) { 
            return 1; 
        } 
        // cat(n)= sum of cat(i)*cat(n-i-1)
        for(int i=0; i<n; i++) { 
            r+=cat(i)*cat(n-i-1); 
        } 
        return r; 
    } 
  
    public static void main(String[] args) { 
        Catalan c = new Catalan(); 
        int n=3;
        for (int i=0; i<n; i++) { 
            System.out.print(c.cat(i) + " "); 
        } 
    } 
}
1 1 2

Dynamic Programming Method for Nth Catalan numbers  

Algorithm

  1. Initialize a variable n and an array c to store Catalan numbers.
  2. Initialize the first two elements of the array as 1 and 1 respectively.
  3. Traverse all the values till n starting from 2 one by one and update the array values as the sum of c[ j ] * c[ i-j-1 ].
  4. Return c[n].

Time Complexity: O(n2)

Please click Like if you loved this article?

Space Complexity: O(n)

Implementation for Nth catalon number

C++ Program

#include<bits/stdc++.h>
using namespace std;

long int cat(int n){ 
    
    long int c[n+1]; 
  
    // Initialisation of first two values 
    c[0]=1;
    c[1]=1; 
  
    for(int i=2; i<=n; i++){ 
        c[i] = 0; 
        for(int j=0; j<i; j++) 
            c[i] += c[j] * c[i-j-1]; 
    } 
  
    // Return last number in array
    return c[n]; 
} 
  
int main(){ 
    int n=3;
    for(int i=0; i<n; i++) 
        cout << cat(i) << " "; 
    return 0; 
}
1 1 2

Java Program

class Catalan{ 
  
    static int cat(int n){ 
        int c[] = new int[n + 2]; 
  
         // Initialisation of first two values 
        c[0]=1;
        c[1]=1; 
      
        for(int i=2; i<=n; i++){ 
            c[i] = 0; 
            for(int j=0; j<i; j++) 
                c[i] += c[j] * c[i-j-1]; 
        } 
      
        // Return last number in array
        return c[n]; 
    } 
    public static void main(String[] args) { 
        int n=3;
        for(int i=0; i<n; i++){ 
            System.out.print(cat(i) + " "); 
        } 
    } 
}
1 1 2

Using the Binomial Coefficient  

Here we will directly use the formula to find the nth Catalan number i.e.

Cn = ( ( 2n! ) / ( (n+1)! n! ) )

Time Complexity: O(n)

Space Complexity: O(1)

Implementation for Nth Catalan numbers

C++ Program

#include<bits/stdc++.h>
using namespace std;

long int biCoef(int n, int m){ 
    long int r=1; 
  
    if(m>(n-m)) 
        m=n-m; 

    for (int i=0; i<m; ++i){ 
        r *= (n-i); 
        r /= (i+1); 
    } 
  
    return r; 
} 

long int cat(int n){ 
    // Calculate value of 2nCn 
    long int c = biCoef(2*n, n); 
  
    // return 2nCn/(n+1) 
    return c/(n+1); 
} 
int main(){
    int n=3;
    for (int i=0; i<n; i++) 
        cout << cat(i) << " "; 
    return 0; 
}
1 1 2

Java Program

class Catalan{ 
  
    static long biCoef(int n, int m){ 
        long r=1; 
      
        if(m>(n-m)) 
            m=n-m; 
    
        for (int i=0; i<m; ++i){ 
            r *= (n-i); 
            r /= (i+1); 
        } 
      
        return r; 
    } 
    
    static long cat(int n){ 
        // Calculate value of 2nCn 
        long c = biCoef(2*n, n); 
      
        // return 2nCn/(n+1) 
        return c/(n+1); 
    } 
    public static void main(String[] args) { 
        int n=3;
        for(int i=0; i<n; i++){ 
            System.out.print(cat(i) + " "); 
        } 
    } 
}
1 1 2

References

See also
Dijkstra Algorithm
Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh