List of Mathematical Algorithms

Gale Shapley Algorithm is an efficient algorithm that is used to solve the Stable Matching problem. It takes O(N^2) time complexity where N is the number of people involved.

We are given an array, we need to find the minimum number of increment and decrement operations (by 1) required to make all the array elements equal. We have explored two approaches where brute force approach take O(N^2) time while the efficient approach O(N logN) time.

We are given a sorted array which might have duplicate elements, our task is to find the minimum number of increment (by 1) operations needed to make the elements of an array unique. We have solved this using two approaches one using two pointers and other using hashmap.

In this article, we have explored different applications of Catalan Numbers such as number of valid parenthesis expressions, number of rooted binary trees with n internal nodes, number of ways are there to cut an (n+2)-gon into n triangles and many more.

We are given two numbers M and N. Our aim is to find the highest power of N that divides Factorial of M (M!). First we have discussed about the Brute Force approach and then we will be discussing this problem using Legendre’s formula.

Kadane's Algorithm is commonly known for Finding the largest sum of a subarray in linear time O(N). We have presented 3 variants of Kadane's Algorithm along with in-depth explanation of basic ideas.

Binary GCD algorithm or Stein's algorithm is an algorithm that calculates two non-negative integer's largest common divisor by using simpler arithmetic operations than the standard euclidean algorithm and it reinstates division by numerical shifts, comparisons, and subtraction operations.

We are given an array and we need to find the minimum number of operations required to make GCD of the array equal to k. Where an operation could be either increment or decrement an array element by 1. We have solved this in O(N log N) time complexity.

Given an array of size N . Find the number of increment (by 1) operations required to make the array in increasing order. In each move, we can add 1 to any element in the array.

In this article, we will develop an approach to find all armstrong numbers in a given range. The approach is to check for each number in the range if it is an armstrong number or not.

In this article, we explored how we can find the number of pairs whose sum is divisible by a given number K. This can be done using brute force approach in O(N^2) time but an efficient approach can reduce it to O(N) time.

We started with an O(N^2) time Integer Multiplication algorithm and it was the first time ever in 1960 that we developed an faster Integer Multiplication algorithm which ran at O(N^1.58) time and now in 2019, we are nearly at the end of this domain with O(N logN) time algorithm.

hese are the papers that you should read and understand to understand how we have improved Integer Multiplication over the years and now in 2020, we are on the verge of completing this domain once for all.

Binary exponentiation is an algorithm to find the power of any number N raise to an number M (N^M) in logarithmic time O(log M). The normal approach takes O(M) time provided multiplication takes constant time.

An Armstrong number is an integer such that the sum of the digits raised to the power of the number of digits is equal to the number itself. We verify it in O(logN * loglogN) time.

Our focus is to find the subset of largest size in which the sum of elements of a pair is not divisible by K. Using mathematical ideas, we solved it in linear time.

In this problem, we to need find the difference between the sum of squares of all numbers from 1 to N and the square of the sum of 1 to N. We solved it in constant time.

Our focus is to find the sum of the quares of the first N numbers that is from 1 to N. With an insightful equation, we can solve this in constant time O(1).

In this problem, we will find the sum of the first N integers that is 1 to N. We can solve this in constant time O(1) by using an insightful formula.

We will find the smallest number that is perfectly divisible by all numbers from 1 to N and used 3 approaches: Brute force O(N^3 * log N), using prime factorization O(N * log N * log N) and using insights into the problem O(N * log log N).