Total number of set-bits from 1 to n

Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n. Example: Input: n = 3 Output: 4 The way to solve these sorts of problems is to write out the first few values, and look for a pattern [...]

By |2018-12-10T23:19:55+05:30December 10th, 2018|Categories: Data Structure|

Strongly Connected Components | Graph

A directed graph is strongly connected if there is a directed path from any vertex to every other vertex. Strong connectivity applies only to directed graphs because in an undirected graph, every vertex can reach every other vertex via any path. This relation between nodes is reflexive, symmetric, and transitive, so it [...]

By |2019-07-07T16:59:52+05:30December 8th, 2018|Categories: Data Structure|

Dijkstra Vs Prim Algorithm | Graph

Prim Algorithm Prim’s algorithm constructs a minimum spanning tree for the graph, which is a tree that connects all nodes in the graph and has the least total cost among all trees that connect all the nodes. However, the length of a path between any two nodes in the MST [...]

By |2020-03-28T14:34:56+05:30December 8th, 2018|Categories: Data Structure|Tags: |

Number of special subsequences in a string

You are given a String S of length N. Now, a special subsequence is one that can be represented in the form a^i b^j c^k, where i≥1, j≥1 and k≥1. In short, a special subsequence is a subsequence that first consist of i ′a′ characters, followed by j ′b′ characters, [...]

By |2018-12-02T16:37:07+05:30December 2nd, 2018|Categories: Data Structure|

Huffman Coding

Prefix Code It is a type of code system distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system. For example, a code with code words [...]

By |2018-11-28T22:44:46+05:30November 28th, 2018|Categories: Data Structure|

Longest proper prefix in KMP

Pattern searching is an important problem. Worst case time complexity of the Naive algorithm is O(m(n-m+1)). The time complexity of KMP algorithm is O(n) in the worst case. Every time the naive function fails (or succeeds), it starts matching over from the next character. This might not be necessary. We [...]

By |2018-11-24T21:22:12+05:30November 24th, 2018|Categories: Data Structure|

Detect Cycle | Graph

Introduction Graphs are of two kinds on the basis of the way edges are directed. In Undirected graph all the edges go forward as well as backward between two vertices. In Directed graph edges between two vertices are directional. Algorithm For Detecting Cycle To detect cycles using DFS, use two [...]

By |2020-03-28T15:04:20+05:30October 7th, 2018|Categories: Data Structure|Tags: |

Important Algorithms

Rabin-Karp Algorithm for Pattern Searching Majority Voting Algorithm Dutch national flag sorting Kahn’s algorithm for Topological Sorting Tarjan’s Algorithm to find Strongly Connected Components Knuth-Morris-Pratt string matching Prim’s Minimum Spanning Tree Flood-fill Algorithm Dijkstra’s shortest path algorithm

By |2018-12-08T14:20:40+05:30October 3rd, 2018|Categories: Data Structure|

Expression Tree

Expression tree is a binary tree in which each internal node corresponds to operator and each leaf node corresponds to operand. Consider the expression: (a + b*c) * ( d + e) It can be represented as a binary tree as In-order traversal, reconstructs the expression:  (a + b*c) * [...]

By |2018-09-21T16:32:16+05:30September 21st, 2018|Categories: Data Structure|
Go to Top