Algorithms that run our Universe

Find the number of subsets of an array having a given XOR value

We are given an array of size N and a value M, we have to find the number of subsets in the array having M as the xor value of all elements in the subset. This can be solved using Dynamic Programming in linear time.

Algorithms

Longest repeating and non overlapping substring in a string

We have to find the longest repeating and non-overlapping substring in a given string. Brute force approach takes O(N^3) time while Dynamic Programming takes O(N^2) time.

Algorithms

Minimum number of Fibonacci terms with sum equal to a given number N

Given a number N, we need to find the minimum number of fibonacci numbers required that sums up to a given number N. Note a fibonacci number can be repeated

Algorithms

Binary exponentiation (Power in log N)

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.

Algorithms

2 Sum Problem: Number of pairs with a given sum

We will find out how we can count the number of pairs in an array whose sum is equal to a certain number. Brute force approaches will take O(N^2) time but we can solve this in O(N) time using a Hash Map.

Algorithms

Shortest Path with k edges using Dynamic Programming

Given a weighted directed graph, we need to find the shortest path from source u to the destination v having exactly k edges. Brute force approach takes O(V^k) time complexity which we reduce to O(V^3 * k) using dynamic programming

Algorithms

Number of paths with k edges using Dynamic programming and Divide and Conquer

Given a directed graph, we need to find the number of paths with exactly k edges from source u to the destination v. A brute force approach has time complexity which we improve to O(V^3 * k) using dynamic programming which we improved further to O(V^3 * log k) using a divide and conquer technique.

Algorithms

Must read research papers on Algorithms

We presented some of the must read research papers in the field of Algorithms. The papers come from authors like C. A. R. Hoare, D. E. Knuth, V. Strassen and many others.

Data Structures

Autocomplete Feature using Ternary Search Tree

Autocomplete Feature can be implemented using Ternary Search Tree as well which is a memory optimized version of trie and performs equally well.

Machine Learning (ML)

PageRank

PageRank is an algorithm to assign weights to nodes on a graph based on the graph structure and is largely used in Google Search Engine being developed by Larry Page

Algorithms

Bozosort

Bozosort is a random sorting algorithms where the key idea is to swap any two elements of the list randomly and check if the list is sorted. The average time complexity of Bozosort is O(N!) and the space complexity is O(1).

Algorithms

Number of ways to pair elements

In this article, we are going to discuss about element pairing problem where we need to find the number of ways a set of elements can be pair or kept separate. This can be solved using Dynamic Programming in linear time O(N).

Algorithms

Finding number of pairs with a certain XOR value

In this article, we are going to find the number of pairs in an unsorted array, whose XOR values matches with our target value (say K). Using our efficient approach (with Hash map), we can solve this in O(N) time complexity while the brute force approach takes O(N^2) time complexity

Algorithms

Check if a number is an Armstrong Number

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.

Algorithms

Number of ways to represent a number N as sum of K Fibonacci terms

The problem we will solve is that given a number N and K, we need to find the numbers of ways we can represent N as a sum of K fibonacci numbers. We will solve this problem efficiently using a recursive technique in O(N).

Algorithms

Autocomplete feature using TRIE Data Structure

Autocomplete is a feature of suggesting possible extensions to a partially written text and is widely used in search engine, code IDEs and much more. Trie data structure is a perfect fit to implement this feature efficient in terms of memory and time [O(length of string)].

Software Engineering

Different ways to add 1 to a number

We compared 8 different techniques to increment a number by 1 by generating the assembly code. It depends on the compiler and language as well.

Algorithms

Break a number in 3 parts (n/2, n/3, n/4) recursively to get maximum sum

Given a number n, we can divide it in only three parts n/2, n/3 and n/4 recursively and find the maximum sum of the 3 parts. This can be solved in linear time using Dynamic Programming

Algorithms

Gnome Sort

Gnome Sort is a simple sorting algorithm with time complexity O(N^2) where the key idea is to swap adjacent elements (if not in order) to sort the entire list

Algorithms

Easiest IMO problems that will make you feel like a Genius

IMO problems are known to be difficult but we have identified 5 problems which you can solve without using a paper. This will make you feel like a GENIUS

Algorithms

Subset of maximum size with no pair sum divisible by 'K'

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.

Algorithms

Difference between square of sum (Σn)² and sum of squares (Σn²)

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.

Algorithms

Sum of squares of first N numbers ( Σ n² )

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

Algorithms

Sum of first N numbers ( Σ n )

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.

Algorithms

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