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 [...]
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 [...]
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 [...]
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, [...]
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 [...]
There is a pyramid with 1 cup at level , 2 at level 2 , 3 at level 3 and so on i.e. 1 2 3 4 5 6 Every cup has capacity C, you pour L liters of water from top. When cup 1 gets filled , it overflows [...]
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 [...]
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 [...]
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 TreeOptimized Version: https://www.geeksforgeeks.org/prims-algorithm-using-priority_queue-stl/ Flood-fill Algorithm Dijkstra’s shortest path algorithmOptimized Version: https://ide.geeksforgeeks.org/Do157gzJig
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) * [...]