Home » Interview Questions » Algorithm Interview Questions » Nth Catalan Number

Nth Catalan Number


()

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. 

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)

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

READ  Container with Most Water

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions