Math Algorithms
What are Mathematical Algorithms?
Mathematical algorithm can be defined as an algorithm or procedure which is utilized to solve a mathematical problem, or mathematical problem which can be solved using DSA.
In the field of DSA, mathematical algorithms refer to those algorithms which are generally used to solve problems related to the field of computer science.
What are some use cases of Mathematical Algorithms?
It is a very useful topic for solving problems of computer science and also has vast applications in competitive programming. Some of them are mentioned below:
- Problem-Solving: It is mostly used in solving complex mathematical ideas in mathematics and computer science.
- Competitive Programming: Algorithms like Sieve of Eratosthenes, Euclid algorithm, Binary exponentiation are some of the most common topics used in competitive programming.
- Recurrence relation: A lot of problems in DSA require the usage of recursion. Using the knowledge of mathematics several recurrence relations can be turned into mathematical formulae which makes solving the problem quite an easy task.
- Heavy calculation: Problems containing complex mathematical concepts and heavy calculations are easily done in comparatively less time using these algorithms instead of manual calculations.
- Statistics: Mathematical algorithms are also important for data processing, i.e., for converting raw data into useful information and also for analyzing them.
Table of Content
- What are Mathematical Algorithms?
- What are some use cases of Mathematical Algorithms?
- Divisibility & Large Numbers:
- GCD and LCM
- Series
- Number Digits
- Algebra
- Number System
- Prime Numbers & Primality Tests
- Prime Factorization & Divisors
- Modular Arithmetic
- Factorial
- Fibonacci Numbers
- Catalan Numbers
- nCr Computations
- Set Theory
- Sieve Algorithms
- Euler Totient Function
- Chinese Remainder Theorem
- Some Practice Problems
Divisibility & Large Numbers:
- Check if a large number is divisible by 3 or not
- Check if a large number is divisible by 4 or not
- Check if a large number is divisible by 6 or not
- Check divisibility by 7
- Check if a large number is divisible by 9 or not
- Check if a large number is divisible by 11 or not
- Divisibility by 12 for a large number
- Check if a large number is divisible by 13 or not
- Check if a large number is divisibility by 15
- Number is divisible by 29 or not
GCD and LCM:
- LCM of array
- GCD of array
- Basic and Extended Euclidean algorithms
- Stein’s Algorithm for finding GCD
- GCD, LCM and Distributive Property
- Count number of pairs (A <= N, B <= N) such that gcd (A, B) is B
- Program to find GCD of floating point numbers
- Series with largest GCD and sum equals to n
- Largest Subset with GCD 1
- Summation of GCD of all the pairs up to N
Series:
- Juggler Sequence
- Padovan Sequence
- Aliquot Sequence
- Moser-de Bruijn Sequence
- Stern-Brocot Sequence
- Newman-Conway Sequence
- Sylvester’s sequence
- Recaman’s sequence
- Sum of the sequence 2, 22, 222, ………
- Sum of series 1^2 + 3^2 + 5^2 + . . . + (2*n – 1)^2
- Sum of the series 0.6, 0.06, 0.006, 0.0006, …to n terms
- n-th term in series 2, 12, 36, 80, 150….
Number Digits:
- Minimum digits to remove to make a number Perfect Square
- Print first k digits of 1/n where n is a positive integer
- Check if a given number can be represented in given a no. of digits in any base
- Find element using minimum segments in Seven Segment Display
- Find next greater number with same set of digits
- Check if a number is jumbled or not
- Numbers having difference with digit sum more than s
- Total numbers with no repeated digits in a range
- K-th digit in ‘a’ raised to power ‘b’
Algebra:
- Program to add two polynomials
- Multiply two polynomials
- Find number of solutions of a linear equation of n variables
- Calculate the Discriminant Value
- Program for dot product and cross product of two vectors
- Iterated Logarithm log*(n)
- Program to find correlation coefficient
- Program for Muller Method
- Number of non-negative integral solutions of a + b + c = n
- Generate Pythagorean Triplets
Number System:
- Exponential notation of a decimal number
- Check if a number is power of k using base changing method
- Convert a binary number to hexadecimal number
- Program for decimal to hexadecimal conversion
- Converting a Real Number (between 0 and 1) to Binary String
- Convert from any base to decimal and vice versa
- Decimal to binary conversion without using arithmetic operators
Prime Numbers & Primality Tests:
Prime Factorization & Divisors:
Modular Arithmetic:
- Modular Exponentiation (Power in Modular Arithmetic)
- Modular multiplicative inverse
- Modular Division
- Euler’s criterion (Check if square root under modulo p exists)
- Find sum of modulo K of first N natural number
- How to compute mod of a big number?
- Exponential Squaring (Fast Modulo Multiplication)
- Trick for modular division ( (x1 * x2 …. xn) / b ) mod (m)
Factorial:
- Program for factorial of a number
- Legendre’s formula (Given p and n, find the largest x such that p^x divides n!)
- Count trailing zeroes in factorial of a number
- Factorial of a large number
- Primorial of a number
- Find maximum power of a number that divides a factorial
- Largest power of k in n! (factorial) where k may not be prime
- Check if a number is a Krishnamurthy Number or not
- Last non-zero digit of a factorial
- Count digits in a factorial using Logarithm
Fibonacci Numbers:
Catalan Numbers:
nCr Computations:
Set Theory:
Sieve Algorithms:
Euler Totient Function:
Chinese Remainder Theorem:
Some Practice Problems:
- Interquartile Range (IQR)
- Simulated Annealing
- Pseudo Random Number Generator (PRNG)
- Square root of a number using log
- Find ways an Integer can be expressed as sum of n-th power of unique natural numbers
- N-th root of a number
- Fast Fourier Transformation for poynomial multiplication
- Find Harmonic mean using Arithmetic mean and Geometric mean
- Double Base Palindrome
- Program for Derivative of a Polynomial
- Sgn value of a polynomial
- Check if a number is a power of another number
- Program to evaluate simple expressions
- Make a fair coin from a biased coin
- Implement *, – and / operations using only + arithmetic operator
Quick Links :
- Learn Data Structure and Algorithms | DSA Tutorial
- Practrice Problems on Mathematical Algorithms
- Quizzes on Mathematical Algorithms
- Videos on Mathematical Algorithms
Contact Us