Catalan Numbers
Catalan numbers are a sequence of natural numbers that have various applications in combinatorial mathematics, particularly in the counting of different types of binary trees, parenthetical expressions, and more.
Formula:
Below is the code snippet for Catalan Numbers:
#include <iostream>
// Function to calculate nth Catalan number
unsigned long long catalan(unsigned int n)
{
if (n == 0 || n == 1)
return 1;
unsigned long long catalan_num = 0;
for (int i = 0; i < n; ++i)
catalan_num += catalan(i) * catalan(n - i - 1);
return catalan_num;
}
int main()
{
unsigned int n = 5;
unsigned long long result = catalan(n);
std::cout << "The " << n
<< "th Catalan number is: " << result
<< std::endl;
return 0;
}
public class Main {
// Function to calculate nth Catalan number
static long catalan(int n)
{
if (n == 0 || n == 1)
return 1;
long catalanNum = 0;
for (int i = 0; i < n; ++i)
catalanNum += catalan(i) * catalan(n - i - 1);
return catalanNum;
}
public static void main(String[] args)
{
int n = 5; // Example input
long nthCatalan = catalan(n);
System.out.println("The " + n
+ "th Catalan number is: "
+ nthCatalan);
}
}
// this code is contributed by Kishan
# Function to calculate nth Catalan number
def catalan(n):
# Base cases
if n == 0 or n == 1:
return 1
# Initialize result
catalan_num = 0
# Catalan number is the sum of catalan(i) * catalan(n - i - 1)
for i in range(n):
catalan_num += catalan(i) * catalan(n - i - 1)
return catalan_num
# Driver code
if __name__ == "__main__":
n = 5
result = catalan(n)
print(f"The {n}th Catalan number is: {result}")
function catalan(n) {
if (n === 0 || n === 1) {
return 1;
}
let catalanNum = 0;
for (let i = 0; i < n; ++i) {
catalanNum += catalan(i) * catalan(n - i - 1);
}
return catalanNum;
}
function main() {
const n = 5; // Example input
const nthCatalan = catalan(n);
console.log("The " + n + "th Catalan number is: " + nthCatalan);
}
main();
Output
The 5th Catalan number is: 42
Maths for Data Structure and Algorithms (DSA) | A Complete Guide
Maths is a fundamental component of learning Data Structure and Algorithms, just like in programming. Maths is primarily used to evaluate the effectiveness of different algorithms. However, there are situations when the answer requires some mathematical understanding or the problem has mathematical characteristics and certain problems demand more than just code. They require a mathematical perspective and a recognition of patterns and characteristics that go beyond the syntax of programming languages. Therefore, understanding maths is essential to know data structures and algorithms. So here in this Maths Guide for Data Structure and Algorithms (DSA), we will be looking into some commonly used concepts of Maths in DSA.
Table of Content
- GCD and HCF (Euclidean Algorithm)
- Divisors of a number
- Prime numbers using Sieve of Eratosthenes
- Square root
- Modular Arithmetic
- Fast Power-Exponentiation by Squaring
- Factorial of a number
- Fibonacci Number
- Catalan Numbers
- Euler Totient Function
- Prime numbers & Primality Tests
- Prime Factorization & Divisors
- Chinese Remainder Theorem
- Practice Problems based on Maths for DSA
- Most Frequently Asked Questions (FAQs)