FilesExpand file tree

 master

/

CatalanNumber.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

60 lines (48 loc) · 1.72 KB

 master

/

CatalanNumber.java

Top

File metadata and controls

• Code
• Blame

60 lines (48 loc) · 1.72 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

package DynamicProgramming;

/**

* This file contains an implementation of finding the nth CATALAN NUMBER using dynamic programming

* Wikipedia: https://en.wikipedia.org/wiki/Catalan_number

*

* Time Complexity: O(n^2)

* Space Complexity: O(n)

*

* @author AMRITESH ANAND (https://github.com/amritesh19)

*/

import java.util.Scanner;

public class CatalanNumber {

/**

* This method finds the nth Catalan number

*

* @param n input n which determines the nth Catalan number

* n should be less than equal to 50 as 50th Catalan number is 6,533,841,209,031,609,592

* for n > 50, BigInteger class should be used instead long

*

* @return catalanArray[n] the nth Catalan number

*/

static long findNthCatalan(int n){

// Array to store the results of subproblems i.e Catalan numbers from [1...n-1]

long catalanArray[] = new long[n + 1];

// Initialising C₀ = 1 and C₁ = 1

catalanArray[0] = 1;

catalanArray[1] = 1;

/**

* The Catalan numbers satisfy the recurrence relation

* C₀=1 and Cn = Σ (Ci * Cn-1-i), i = 0 to n-1 , n > 0

*/

for(int i = 2; i <= n; i++){

catalanArray[i] = 0;

for(int j = 0; j < i; j++){

catalanArray[i] += catalanArray[j] * catalanArray[i - j - 1];

}

}

return catalanArray[n];

}

// Main method

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

System.out.println("Enter the number n to find nth Catalan number (n <= 50)");

int n = sc.nextInt();

System.out.println(n + "th Catalan number is " + findNthCatalan(n));

sc.close();

}

}