Sorting an array seems like an easy process especially when the dataset is small. But what to do when the data is large or may contain 1000s of entries? No matter which sorting algorithm you use, the time and space required in your system will increase. However, to avoid this issue, an inversion count is done. An inversion count simply determines how close your array is to being sorted. For instance, if you are asked to sort array of 0 1 2 , the inversion count will determine how many times the elements will change their positions to give a sorted array. After knowing that, you can apply the sorting algorithm which seems feasible. However, if the array is already sorted, inversion count will save all your effort to go through the process of sorting. But how do you count inversions in an array? To count inversions in an array , multiple approaches are followed. Here, we have discussed all the approaches in detail. So, keep reading! Methods To Count Inversions In An Array Method 1...

Introduction The objective is to write a function that returns true (or 1) if a given undirected graph is a tree and false (or 0) if it is not a tree. A graph can be classified as a tree if it satisfies the following two conditions: - Each node, except the root node, must have a single parent. That is, each node must be reached only from its parent when the tree is being traversed starting from the root. We must be able to visit all the nodes of the tree starting from the root. Therefore, a tree should always be connected, and all nodes must be reachable.   Problem Statement Let us consider two graphs as shown in the figure below:   Figure 1  shows a valid tree as it has no cycles, and has n-1 edges for n nodes. Figure 2  is invalid as it contains a cycle connecting 1 and 2. A function is to be written that returns 1 if the given graph is a valid tree and 0 if it is not a valid tree. (Check out the details for the problem of the  graph valid tree )   Psuedo...