11) Prime numbers & Primality Tests

1) GCD and HCF (Euclidean Algorithm)

The GCD or HCF of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder....

2) Divisors of a number

A divisor is a number that gives remainder as 0 when divided....

3) Prime numbers using Sieve of Eratosthenes

A prime number is a natural number greater than 1 and is divisible by only 1 and itself....

4) Square root

To find the floor of the square root, try with all-natural numbers starting from and continue incrementing the number until the square of that number is greater than the given number. but this will take linear time complexity .So can we optimize to better complexity , answer is yes , the idea is to find the largest integer i whose square is less than or equal to the given number. The values of  i*i is monotonically increasing, so the problem can be solved using binary search....

5) Modular Arithmetic

Basically, modular arithmetic is related with computation of “mod” of expressions.some important identities about the modulo operator:...

6) Fast Power-Exponentiation by Squaring

We know how to find 2 raised to the power 10. But what if we have to find 2 raised to the power very large number such as 1000000000? Exponentiation by Squaring helps us in finding the powers of large positive integers. Idea is to the divide the power in half at each step....

7) Factorial of a number

Factorial of a non-negative integer is the multiplication of all positive integers smaller than or equal to n. For example factorial of 6 is 6*5*4*3*2*1 which is 720....

8) Fibonacci Number

The Fibonacci series is the sequence where each number is the sum of the previous two numbers of the sequence. The first two numbers of the Fibonacci series are 0 and 1 and are used to generate the Fibonacci series....

9) 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....

10) Euler Totient Function

Euler’s Totient Function, denoted as ϕ(n), gives the count of positive integers less than or equal to n that are relatively prime to n....

11) Prime numbers & Primality Tests

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, a prime number is only divisible by 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, and so on. Prime numbers play a crucial role in number theory and various areas of computer science, including cryptography and algorithm design....

12) Prime Factorization & Divisors

Prime Factorization: Expressing a number as a product of its prime factors.Example:...

13) Chinese Remainder Theorem

Given a system of simultaneous congruences, the Chinese Remainder Theorem provides a unique solution modulo the product of the moduli if the moduli are pairwise coprime....

Practice Problems based on Maths for DSA:

Problem Link Prime Numbers Solve Basic and Extenden Euclidean Algorithm Solve Factorial Solve LCM and GCD Solve Nth Fibonacci Number Solve Program to multiply two matrices Solve Nth catalan number Solve Write program to calculate pow(x, n) Solve Find all factors of a Natural Number Solve Modular Exponentiation Solve...

Most Frequently Asked Questions (FAQs):

Question 1: Why is mathematics important for understanding Data Structures and Algorithms?...