Find Number of reverse pairs in an array
Objective: Given an array of integers A[],find no of reverse pairs means no of (i, j) pairs where i < j and A[i]>A[j]. Example: A[] = {10, 3, 4, 2, 5, 7, 9, 11}...
Tagged: Intermediate
Heap Sort – Java Implementation
What is Heap Sort?? Heap sort is comparison based sorting algorithm. Heap sort is considered as improved selection sort, it divides the input into sorted and unsorted region. The improvement from selection sort is...
Get the Sum of Digits in a number till it become a single digit
Objective – Given a number, Write a program to get the sum of digits in a number till it become a single digit. Example: N = 999 -> 9+9+9 = 27-> 2+7 = 9...
Check if given number is Prime – O(√N) Solution – Java Program
Objective: Given a number, write a program to check if the number is prime or not. Prime Number: A number is called a prime number when number is not divisible by 1 or by...
Swap two numbers using Bitwise XOR Operator
Objective– Given two numbers, swap both the numbers using XOR operators. Example: X = 4, Y = 8 Output: X = 8, Y= 4 Approach: XOR operator There are many ways to swap two...
Find number of Distinct Permutations of a String
Objective – Given a string, find the number of distinct permutations or anagrams of that string. Example: String x = “abc” Output: 6 (abc, acb, bac, bca, cab, cba) String x = “aab” Output:...
Replace all vowels with next consonant in a given string
Objective: Given a string, write an algorithm to replace all the vowels with next consonant, and if last alphabet is vowel, remove it. Example: String input: “abcdefg” Output: “bbcdffg” String input: “aaaabccceee” Output: “bbbbbccc”...
Introduction to Minimum Spanning Tree (MST)
What is a Spanning Tree? In an undirected and connected graph G=(V,E), a spanning tree is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges. A graph...
Graph – Count all paths between source and destination
Objective: Given a graph, source vertex and destination vertex. Write an algorithm to count all possible paths between source and destination. Condition: Graph does not contain any cycle. This problem also known as “paths...
Graph – Find Number of non reachable vertices from a given vertex
Objective: Given undirected graph write an algorithm to count the number of non reachable vertices from a given vertex Example: Approach: Use DFS Do the DFS (Depth-First Search) from the given vertex A, Recursively...
Graph – Detect Cycle in an Undirected Graph using DFS
Objective: Given undirected graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Earlier we have seen how to find cycles in directed graphs. In this article we will...
Graph – Detect Cycle in a Directed Graph
Objective: Given a directed graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Graph contains cycle if there are any back edges. There are two types of back...
Graph – Software Installation Problem
Objective: Given a list of software’s which you need to install in a computer. Few software’s has dependency on other software’s in the list, means these software can be installed only when all of...
Graph – Depth First Search in Disconnected Graph
Objective: Given a Graph in which one or more vertices are disconnected, do the depth first traversal. Earlier we have seen DFS where all the vertices in graph were connected. In this article we...
Topological Sort
Topological Sort: A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. A topological ordering is possible if and only if the graph has no directed...