Given a number N. The task is to find the N^{th} catalan number.
The first few Catalan numbers for N = 0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
Catalan Number for N is equal to the number of expressions containing N pairs of paranthesis that are correct matched, i.e., for each of the N '(' there exist N ')' on there right and vice versa.
Note: Positions start from 0 as shown above.
Example 1:
Input:
N = 5
Output: 42
Example 2:
Input:
N = 4
Output: 14
Your Task:
Complete findCatalan() function that takes n as an argument and returns the N^{th} Catalan number. The output is printed by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Mathematics

Starter code: #User function Template for python3

class Solution:
    #Function to find the nth catalan number.
    def findCatalan(self,n):
        #return the nth Catalan number.

Solutions:
class Solution:

	def findCatalan(self, n):
		table = [1 for i in range(n + 1)]
		for i in range(1, n + 1):
			x = 1
			y = 1
			for j in range(2, i + 1):
				x = x * (i + j)
				y = y * j
			table[i] = int(x // y)
		return table[n]


class Solution:

	def findCatalan(self, n):
		catalan = [0] * (n + 1)
		catalan[0] = 1
		catalan[1] = 1
		for i in range(2, n + 1):
			for j in range(i):
				catalan[i] += catalan[j] * catalan[i - j - 1]
		return catalan[n]


class Solution:

	def findCatalan(self, n):
		dp = [0] * (n + 1)
		dp[0] = 1
		dp[1] = 1
		if n <= 1:
			return 1
		for i in range(2, n + 1):
			for j in range(i):
				dp[i] += dp[j] * dp[i - j - 1]
		return dp[n]


def factorial(n):
	if n == 0:
		return 1
	else:
		return n * factorial(n - 1)

class Solution:

	def findCatalan(self, n):
		c = factorial(2 * n) // (factorial(n + 1) * factorial(n))
		return c


class Solution:

	def findCatalan(self, n):
		table = [0 for i in range(n + 1)]
		table[0] = 1
		table[1] = 1
		for i in range(2, n + 1):
			s = 0
			for j in range(i):
				s = s + table[j] * table[i - j - 1]
			table[i] = s
		return table[-1]


from typing import Optional, Dict

class Solution:

	def findCatalan(self, n: int, memo: Optional[Dict[int, int]]=None) -> int:
		if n <= 1:
			return 1
		if memo is not None and n in memo:
			return memo[n]
		value = self.findCatalan(n - 1, memo) * (4 * n - 2) // (n + 1)
		if memo is None:
			memo = {n: value}
		else:
			memo[n] = value
		return value


class Solution:

	def findCatalan(self, n):
		num = 1
		den = 1
		for i in range(1, n + 1):
			num *= i + n
			den *= i
		num = num // (n + 1)
		return num // den


class Solution:

	def findCatalan(self, n):
		N = self.fact(2 * n)
		D1 = self.fact(n + 1)
		D2 = self.fact(n)
		return N // (D1 * D2)

	def fact(self, n):
		if n == 1:
			return 1
		else:
			return n * self.fact(n - 1)


class Solution:

	def findCatalan(self, n):
		stateMap = [[0 for i in range(n + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			stateMap[i][0] = 1
		for r in range(1, n + 1):
			for c in range(1, r + 1):
				stateMap[r][c] = stateMap[r][c - 1] + stateMap[r - 1][c]
		return stateMap[n][n]


def catalan_numbers(n):
	if n == 0:
		return 1
	else:
		return (4 * n - 2) * catalan_numbers(n - 1) // (n + 1)

class Solution:

	def findCatalan(self, n):
		return catalan_numbers(n)


from math import factorial

class Solution:

	def findCatalan(self, n):
		k = factorial(2 * n) // (factorial(n) * factorial(n + 1))
		return k


class Solution:

	def findCatalan(self, n):
		cat_ = 1
		for i in range(1, n + 1):
			cat_ *= 4 * i - 2
			cat_ //= i + 1
		return cat_


from math import factorial as fact

class Solution:

	def findCatalan(self, n):
		return fact(2 * n) // (fact(n + 1) * fact(n))


class Solution:

	def findCatalan(self, n):
		x = 1
		for i in range(1, n + 1):
			x = x * i
		z = 1
		for j in range(1, 2 * n + 1):
			z = z * j
		return z // (x * x * (n + 1))


class Catlan_number:

	def __init__(self) -> None:
		self.catlan_dict = [1, 1]

	def get_catlan(self, N):
		if len(self.catlan_dict) > N:
			return self.catlan_dict[N]
		else:
			num = 1
			den = 1
			for i in range(1, N + 1):
				num *= i + N
				den *= i
				self.catlan_dict.append(num // (N + 1) // den)
			return self.catlan_dict[N + 1]

class Solution:

	def __init__(self) -> None:
		self.C = Catlan_number()

	def findCatalan(self, n):
		return self.C.get_catlan(n)


from math import *

class Solution:

	def findCatalan(self, n):
		catalan = lambda n: factorial(2 * n) // factorial(n) // factorial(n) // (n + 1)
		return catalan(n)


class Solution:

	def findCatalan(self, n):
		l = [1 for i in range(n + 1)]
		for i in range(2, n + 1):
			l[i] = 2 * i * (2 * i - 1) * l[i - 1] // ((i + 1) * i)
		return l[-1]


class Solution:

	def findCatalan(self, n):
		table = [0 for i in range(n + 1)]
		for j in range(n + 1):
			if j == 0:
				table[0] = 1
				continue
			elif j == 1:
				table[1] = 1
				continue
			else:
				ans = 0
				for i in range(j):
					ans += table[i] * table[j - i - 1]
			table[j] = ans
		return table[n]


class Solution:

	def findCatalan(self, n):
		curr = 1
		for num in range(0, n):
			new = 2 * (2 * num + 1) * curr // (num + 2)
			curr = new
		return curr


class Solution:

	def findCatalan(self, n):
		dp = [1, 1]
		for i in range(2, n + 1):
			ci = dp[i - 1] * (2 * i - 1) * (2 * i) // ((i + 1) * i)
			dp.append(ci)
		return dp[-1]


import math

class Solution:

	def findCatalan(self, n):
		Num = math.factorial(2 * n)
		Den = math.factorial(n + 1) * math.factorial(n)
		return Num // Den


from decimal import *

class Solution:

	def findCatalan(self, n):
		getcontext().prec = 100
		num1 = Decimal(1)
		for i in range(1, n + 1):
			num2 = num1 * Decimal(i * 2) * Decimal(i * 2 - 1) / Decimal(i + 1) / Decimal(i)
			num1 = num2
		return int(num1)


import math

class Solution:

	def findCatalan(self, n):
		num = math.factorial(2 * n)
		den = math.factorial(n + 1) * math.factorial(n)
		return num // den


class Solution:

	def findCatalan(self, n):

		def fact(a):
			if a == 0 or a == 1:
				return 1
			return a * fact(a - 1)
		return fact(2 * n) // (fact(n + 1) * fact(n))


def nthKatalan(n):
	total = 1
	for i in range(n + 2, 2 * n + 1):
		total *= i
	for i in range(1, n + 1):
		total //= i
	return total

class Solution:

	def findCatalan(self, n):
		return nthKatalan(n)


class Solution:

	def findCatalan(self, n):
		dp = [-1] * (n + 1)

		def catalan(n):
			if n <= 1:
				return 1
			if dp[n] != -1:
				return dp[n]
			res = 0
			for i in range(n):
				res += catalan(i) * catalan(n - i - 1)
			dp[n] = res
			return res
		return catalan(n)


class Solution:

	def findCatalan(self, n):
		return self.nthCatalan(n, {})

	def nthCatalan(self, n, pathcheck):
		if n == 0 or n == 1:
			return 1
		ways = 0
		currentKey = n
		if currentKey in pathcheck:
			return pathcheck[currentKey]
		for i in range(0, n - 1 + 1):
			ways += self.nthCatalan(i, pathcheck) * self.nthCatalan(n - i - 1, pathcheck)
		pathcheck[currentKey] = ways
		return ways


class Solution:

	def findCatalan(self, n):
		if n == 0:
			return 1
		return self.findCatalan(n - 1) * 2 * (2 * n - 1) // (n + 1)


import math

def fact(n):
	if n == 1:
		return 1
	return n * fact(n - 1)

class Solution:

	def findCatalan(self, n):
		dp = [0] * (n + 1)
		(dp[0], dp[1]) = (1, 1)
		for i in range(2, n + 1):
			for j in range(0, i):
				dp[i] += dp[j] * dp[i - j - 1]
		return dp[n]
		a = math.factorial(2 * n) / math.factorial(n - 1)
		a = a / math.factorial(2 * n - n + 1)
		a = a / n
		return int(a)


class Solution:

	def findCatalan(self, n):
		if n == 0 or n == 1:
			return 1
		k = 2 * n
		count = 3
		list1 = [1, 2]
		for i in range(1, k):
			list1.append(list1[-1] * count)
			count = count + 1
		ans = list1[k - 1] // (list1[n] * list1[n - 1])
		return ans


class Solution:

	def findCatalan(self, n, memo={}):
		if n in memo:
			return memo[n]
		if n <= 1:
			return 1
		res = 0
		for i in range(n):
			res += self.findCatalan(i, memo) * self.findCatalan(n - i - 1, memo)
		memo[n] = res
		return res


class Solution:

	def gcd(self, a, b):
		r = a % b
		while r != 0:
			a = b
			b = r
			r = a % b
		return b

	def findCatalan(self, n):
		nem = 1
		deno = 1
		for i in range(2, n + 1):
			nem *= n + i
			deno *= i
			g = self.gcd(nem, deno)
			nem = nem // g
			deno = deno // g
		return nem


class Solution:

	def findCatalan(self, n):
		bino_N = [1, 1]
		for N in range(2, n * 2 + 1):
			bino = []
			for r in range(N + 1):
				if r == 0 or r == N:
					bino.append(1)
				else:
					bino.append(bino_N[r] + bino_N[r - 1])
			bino_N = bino
		return bino_N[n] - bino_N[n + 1]


import math

class Solution:

	def findCatalan(self, n):
		a = math.factorial(2 * n)
		b = math.factorial(n) * math.factorial(n + 1)
		return a // b


import math

class Solution:

	def findCatalan(self, n):
		c = math.factorial(2 * n) // (math.factorial(n + 1) * math.factorial(n))
		return int(c)


class Solution:

	def findCatalan(self, n):
		s = Solution()
		return s.fact(2 * n) // (s.fact(n) * s.fact(n + 1))

	def fact(self, n):
		f = 1
		for i in range(2, n + 1):
			f = f * i
		return f


class Solution:

	def findCatalan(self, n):

		def factoiral(n):
			if n == 1 or n == 0:
				return 1
			return n * factoiral(n - 1)
		ans = factoiral(2 * n) // (factoiral(n + 1) * factoiral(n))
		return int(ans)


class Solution:

	def findCatalan(self, n):
		p = 1
		s = 1
		for i in range(1, n + 1):
			p *= i + n
			s *= i
		p = p // (n + 1)
		return p // s


class Solution:

	def findCatalan(self, n):

		def factorial(x):
			fact = 1
			while x:
				fact = fact * x
				x = x - 1
			return fact
		res = factorial(2 * n) // (factorial(n + 1) * factorial(n))
		return res


class Solution:

	def findCatalan(self, n):
		fact = [1]
		x = len(fact)
		while x < 2 * n + 1:
			entry = x * fact[-1]
			x += 1
			fact.append(entry)
		return fact[2 * n] // (fact[n + 1] * fact[n])


class Solution:

	def findCatalan(self, n):

		def factorial(n):
			f = 1
			for i in range(1, n + 1):
				f *= i
			return f
		t = factorial(2 * n) // (factorial(n) * factorial(n))
		return t // (n + 1)


class Solution:

	def findCatalan(self, n):
		cache = {(n, n): 1}

		def dfs(l, r):
			if (l, r) in cache:
				return cache[l, r]
			if l == n:
				t = dfs(l, r + 1)
			elif l > r:
				t = dfs(l + 1, r) + dfs(l, r + 1)
			elif l == r:
				t = dfs(l + 1, r)
			cache[l, r] = t
			return t
		return dfs(0, 0)


class Solution:

	def findCatalan(self, n):
		arr = [1, 1]
		for i in range(2, n + 1):
			l = 0
			h = i - 1
			sum = 0
			while l <= h:
				if l == h:
					sum += arr[l] * arr[h]
				else:
					sum += arr[l] * arr[h] + arr[h] * arr[l]
				l += 1
				h -= 1
			arr.append(sum)
		return arr[-1]


class Solution:

	def findCatalan(self, n):
		M = [1] * (2 * n + 1)
		M[0] = 1
		M[1] = 1
		for i in range(2, 2 * n + 1):
			M[i] = M[i - 1] * i
		x = M[n] * M[n + 1]
		cat = M[2 * n] // x
		return cat


class Solution:

	def findCatalan(self, n):
		l = n + 1
		catalanNums = [0 for i in range(l)]
		catalanNums[0] = 1
		catalanNums[1] = 1
		for i in range(2, l):
			for j in range(i):
				catalanNums[i] += catalanNums[j] * catalanNums[i - j - 1]
		return catalanNums[n]


class Solution:

	def findCatalan(self, n):
		cat_num = 1
		cat_din = 1
		if n <= 1:
			return cat_num
		else:
			for i in range(2, n + 1):
				cat_num *= n + i
				cat_din *= i
			return cat_num // cat_din


import math

class Solution:

	def findCatalan(self, n):
		l = [1, 1]
		for i in range(2, n + 1):
			k = 0
			for j in range(i):
				k += l[j] * l[i - j - 1]
			l.append(k)
		return l[n]


class Solution:

	def findCatalan(self, n):
		if n == 0 or n == 1:
			return 1
		c = [0] * (n + 1)
		(c[0], c[1]) = (1, 1)
		for i in range(2, n + 1):
			for j in range(i):
				c[i] += c[j] * c[i - j - 1]
		return c[n]


class Solution:

	def findCatalan(self, n):
		if n == 0:
			return 1
		cat = 1
		for i in range(1, n + 1):
			cat *= 4 * i - 2
			cat //= i + 1
		return cat


class Solution:

	def findCatalan(self, n):
		dp = []
		a = 0
		for i in range(n + 1):
			if i <= 1:
				dp.insert(i, 1)
			elif i > 1:
				dp.insert(i, 0)
				for j in range(i):
					a = dp[j] * dp[i - j - 1]
					dp[i] = dp[i] + a
		return dp[n]


class Solution:

	def findCatalan(self, n):
		if n == 0:
			return 1
		N = 2 * n
		res = 1
		for i in range(1, n + 1):
			res *= N
			res //= i
			N -= 1
		return res // (n + 1)


class Solution:

	def findCatalan(self, n):
		dp = [1]
		for i in range(1, n + 1):
			(j, k) = (0, i - 1)
			temp = 0
			while j < i:
				temp += dp[j] * dp[k]
				j += 1
				k -= 1
			dp.append(temp)
		return dp[-1]


class Solution:

	def findCatalan(self, n):
		dp = [1, 1]
		for i in range(2, n + 1):
			s = 0
			for j in range(0, i):
				s += dp[j] * dp[i - j - 1]
			dp.append(s)
		return dp[n]


class Solution:

	def findCatalan(self, n):
		dp = [1, 1]
		for i in range(2, n + 1):
			h = i - 1
			l = 0
			s = 0
			while l <= h:
				if l == h:
					s += dp[h] * dp[l]
				else:
					s += dp[h] * dp[l] + dp[h] * dp[l]
				l += 1
				h -= 1
			dp.append(s)
		return dp[n]


class Solution:

	def findCatalan(self, n):
		mt = [0] * (n + 1)
		mt[0] = 1
		mt[1] = 1
		for k in range(2, n + 1):
			res = 0
			for i in range(0, k):
				res += mt[i] * mt[k - i - 1]
			mt[k] = res
		return mt[n]


class Solution:

	def findCatalan(self, n):

		def ncr(n, r):
			ans = 1
			r = min(r, n - r)
			for i in range(0, r):
				ans = ans * (n - i)
				ans = ans // (i + 1)
			return ans
		ans = ncr(2 * n, n)
		ans = ans // (n + 1)
		return ans


class Solution:

	def findCatalan(self, n):

		def helper(a, dp):
			if a == 0 or a == 1:
				return 1
			if dp[a] != -1:
				return dp[a]
			ans = 0
			for i in range(a):
				val1 = helper(i, dp)
				val2 = helper(a - i - 1, dp)
				ans += val1 * val2
			dp[a] = ans
			return dp[a]
		dp = []
		for i in range(n + 1):
			dp.append(-1)
		return helper(n, dp)


class Solution:

	def fact(self, num):
		if num == 0:
			return 1
		else:
			return num * self.fact(num - 1)

	def findCatalan(self, n):
		ans = self.fact(2 * n) // (self.fact(n + 1) * self.fact(n))
		return ans


class Solution:

	def findCatalan(self, n):
		if n < 1:
			return n
		catalan = [0 for _ in range(n + 1)]
		catalan[0] = 1
		for i in range(1, n + 1):
			for j in range(i):
				catalan[i] += catalan[j] * catalan[i - 1 - j]
		return catalan[n]


class Solution:

	def findCatalan(self, n):
		return self.nthcatalan(n, {})

	def nthcatalan(self, n, memo):
		if n == 0 or n == 1:
			return 1
		currentKey = n
		if currentKey in memo:
			return memo[currentKey]
		ways = 0
		for i in range(n):
			ways += self.nthcatalan(i, memo) * self.nthcatalan(n - i - 1, memo)
		memo[currentKey] = ways
		return memo[currentKey]