algorithm Smallest number with all numbers from 1 to N as multiples 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).
algorithm Largest palindrome made from product of two 3-digit numbers We will find the largest palindrome that is a product of two three-digit numbers. In brute force, there are 810000 comparisons which we have reduced to 362 computations based on three deep insights.
algorithm Largest prime factor of a number (Project Euler Problem 3) We need to find the largest prime factor of a given number N. We will bring in some insights and solve this in O(√N log log N) time complexity.
algorithm Sum of Even Fibonacci Numbers (Project Euler Problem 2) The problem is find the sum of even fibonacci numbers that is fibonacci numbers that are even and is less than a given number N. We will present 3 insightful ideas to solve this efficiently.
algorithm Sum of multiples of 3 and 5 (Project Euler Problem 1) The problem at hand is to find the sum of all numbers less than a given number N which are divisible by 3 and/ or 5 using a constant time algorithm.
algorithm Find point of 2D Line Intersection The point of intersection of two 2D lines can be calculated using two algorithms namely Elimination method and Determinant method which takes constant time O(1)
algorithm Secant Method to find root of any function Secant Method is a numerical method for solving an equation in one unknown. It avoids this issue of Newton’s method by using a finite difference to approximate the derivative.
algorithm Newton Raphson Method to find root of any function Newton's Method, also known as Newton-Raphson method, named after Isaac Newton and Joseph Raphson, is a popular iterative method to find a good approximation for the root of a real-valued function f(x) = 0.
algorithm Regula Falsi Method for finding root of a polynomial Regula Falsi method or the method of false position is a numerical method for solving an equation in one unknown. It is quite similar to bisection method algorithm and is one of the oldest approaches.
algorithm Bisection Method for finding the root of any polynomial Bisection Method for root finding (also called the interval halving method, the binary search method, or the dichotomy method) is based on the Bolzano’s theorem for continuous functions
algorithm Find all primes with Sieve of Sundaram Sieve of Sundaram is an efficient algorithm used to find all the prime numbers till a specific number say N.
algorithm Finding the Lexicographical Next Permutation in O(N) time complexity In Lexicographical Permutation Algorithm we will find the immediate next smallest Integer number or sequence permutation. Finding all permutations take O(N!) time complexity but we present an efficient algorithm which can solve this in O(N) time complexity
algorithm Heap’s algorithm for generating permutations Heap's Algorithm is used to generate all the possible permutation of n-decimals of a number. It generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed. For N numbers, it takes O(N!) time complexity
algorithm Number of unique partitions of an integer Given a positive integer, the problem is to find all the Unique Partitions of the number. We can understand the above problem using some basic examples. Naive approach takes O((N^N)log N) time complexity while Dynamic programming takes O(2^N)
algorithm Distance between two points in 2D space Distance between two points is calculated by creating a right-angled triangle using the two points.The line between the two points is the hypotenuse (the longest side, opposite to the 90° angle). We used the Distance formula derived from Pythagorean theorem with a time complexity of O((log N)^2)
algorithm Area of Polygon: Shoelace formula Given coordinates of vertices of polygon, Area of Polygon is calculated using Shoelace formula described by Mathematician and Physicist Carl Friedrich Gauss where polygon vertices are described by their Cartesian coordinates in the Cartesian plane. The time complexity is O(N) with O(1) space
algorithm Extended Euclidean Algorithm We will demonstrate Extended Euclidean Algorithm. We will see how you can calculate the greatest common divisor in a naive way which takes O(N) time complexity which we can improve to O(log N) time complexity using Euclid's algorithm. Extended Euclidean Algorithm takes O(log N) time complexity
algorithm Sieve of Atkin Sieve of Atkin is an algorithm used to find all prime numbers upto a given number (say N) and does so in O(N) time complexity. With a modified version with enumerating lattice points variation, the time complexity goes to O(N / log log N). It is computationally efficient than Sieve of Eratosthenes
algorithm Area of Triangle: Heron's formula We take a look at Heron's formula which will enable us to calculate the area of any triangle given the length of the three sides of that triangle. The advantage is that the area is calculated using arithmetic operations and hence, the time taken can be assumed to be constant,
algorithm Number of arithmetic progression subsequences in a given set of numbers The problem is that given an array of n positive integers. The task is to count the number of Arithmetic Progression subsequence in the array. This can be solved using dynamic programming in linear time complexity.
algorithm Find the Longest Arithmetic Progression using Dynamic Programming The problem we will solve is that given a set of integers in sorted order, find length of longest arithmetic progression in that set. This can be solved by brute force in O(N^3) while a dynamic programming approach with take O(N^2) time complexity.
game theory Zobrist Hashing Algorithm Complexity Implementations Applications Questions Reading time: 15 minutes | Coding time: 5 minutes Zobrist hashing (additionally alluded to as Zobrist keys or Zobrist marks ) is a hash function development utilized as a part
game theory Alpha Beta Pruning in Minimax Algorithm Algorithm Complexity Implementations Applications Questions Reading time: minutes | Coding time: minutes Like we discussed in earlier article, a hard coded AI can be used to create an intelligent opponent which you can challenge
game theory Von Neumann's Minimax Theorem/ algorithm Introduction Algorithm Complexity Implementations Applications Questions Reading time: 25 minutes | Coding time: 10 minutes Ever since the idea of artificial intelligence dawned upon the humanity, the basic concept of playing games against an
bitwise operation Detect if a number is power of 4 using bitwise operators Reading time: 15 minutes | Coding time: 2 minutes Algorithm Implementation Complexity Questions Bitwise operators are one of the most under-rated operators in C/C++, despite being quite fast as most of the processors
