{"id":1211,"date":"2020-06-10T16:19:59","date_gmt":"2020-06-10T16:19:59","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1211"},"modified":"2022-06-17T06:33:01","modified_gmt":"2022-06-17T06:33:01","slug":"find-the-inversion-count","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/find-the-inversion-count\/","title":{"rendered":"Find the Inversion Count"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Sorting<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

Find number of pairs such that a[i]<\/code> > a[j]<\/code> and i<\/code> < j<\/code>.<\/p>\n<\/blockquote>\n

Test Case<\/h4>\n
    Input:\n    1\n    5\n    10 50 20 40 30\n\n    Output:\n    4\n\n    Explanation:\n    Such required pairs are (50,20),(50,40),(50,30) and (40,30). So, 4 is our answer.<\/code><\/pre>\n
<\/strong><\/u><\/a><\/p>\n
Solving Approach :<\/h3>\n
Bruteforce Approach<\/strong>:<\/p>\n
\n
We can count for each element, such a number of elements on it’s right which are smaller to the current element, this gives us the number of inversions for the current element, hence it can be calculated for all elements in the array. But this approach takes O(n2<\/sup>) time, which is not efficient for larger array sizes. Hence we can solve it more efficiently by following approach which takes O(n\\times{log(n)})<\/code> time.<\/p>\n<\/blockquote>\n
Efficient Approach<\/strong>:<\/p>\n
\n
1) We can count the total number of inversions during sorting array using Merge Sort Algorithm<\/em><\/strong>.
\n2) In the merge sort algorithm when we merge two halves of the array, we copy elements from two halves into the auxiliary array. If the element from the left half is greater than the current right half element, that is also our one inversion as the left element has a lower index than the element in the right half.
\n3) Total number of inversions in above step would be (mid-1)<\/code> because left and right subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] \u2026 a[mid]) will be greater than a[j].
\nSo we count all these inversions and print them as the answer. <\/p>\n<\/blockquote>\n
Example<\/h3>\n
\n
As we saw in, the efficient approach we can count inversions during the merge sort itself. Let array A<\/code> be,<\/p>\n<\/blockquote>\n
\"\"<\/p>\n
\n
Drawing recursion tree for given array, explains a lot about it,<\/p>\n<\/blockquote>\n
\"\"<\/p>\n
\n
Here, while merging, we can see right<\/code> child<\/code> have a inversion (40,30)<\/code>, we add this to our inversion count and move to next step.<\/p>\n
\"\"<\/p>\n
Here again, while merging on the left<\/code> child<\/code>, we observe an inversion (50,20)<\/code>, we add this to our inversion count and move further.<\/p>\n<\/blockquote>\n
\"\"<\/p>\n
\n
In this step, we see that right child<\/code> have two elements which are less than last element of left<\/code> child<\/code>, hence both will be counted as inversions (50,30),(50,40)<\/code>. We count both and move further.<\/p>\n<\/blockquote>\n
\"\"<\/p>\n
\n
Now, we have our array sorted, which means there exists no inversion anymore, so we print count and terminate the program.<\/p>\n<\/blockquote>\n
Solutions<\/h3>\n
\t\t\t\t\t\t