Question

c++ is the language

Code an O(nlog(n)) algorithm to count the number of inversions

DO NOT ADD OR EDIT FUNCTIONS USE THESE ONLY

DO NOT EDIT THE TEST FILE EITHER

countInv.cpp

#include <vector>
#include <algorithm>

using namespace std;

int mergeInv(vector<int>& nums, vector<int>& left, vector<int>& right) {
// You will need this helper function that calculates the inversion while merging
// Your code here

}

int countInv(vector<int>&nums) {
// Your code here

}

countInv_test.cpp

#include <iostream>
#include <vector>

using namespace std;

int countInv(vector<int>& numvec);

int main()
{
    int n;
    vector<int> numvec{4, 5, 6, 1, 2, 3};
    n = countInv(numvec);
    cout << "Number of inversions " << n << endl; // Should be 9
  
    numvec = {1, 2, 3, 4, 5, 6};
    n = countInv(numvec);
    cout << "Number of inversions " << n << endl; // Should be 0
  
    numvec = {6, 5, 4, 3, 2, 1};
    n = countInv(numvec);
    cout << "Number of inversions " << n << endl; // Should be 15
  
    numvec = {0, 0, 0, 0, 0, 0};
    n = countInv(numvec);
    cout << "Number of inversions " << n << endl;; // Should be 0
}

Answer 1

Count Inversion can be solved using merge sort technique in O(nlogn) complexity.

Step1 : Divide the array into two parts recursively then call the merge function to arrange the array in sorted manner.

Step2 : While Merging , whenever element in left part is greater than the element in right part , it means that all the rest of the elements in the left part including the current element satisfies this condition . So we add all
remaining elements of the left part in our answer.

Code Explanation:

1 - Divide the array into two parts i.e left and right
Note: if array length is 1 then we will simply return 0 as inversion is possible only in pairs.

2 - we call the function recursively on left and right and then merge them.

3 - Merge left and right and whenever left[i] > right[j] all the afterwards elements of left i.e [ left.size()-i] gets added to the answer.

Code :

#include <iostream>
#include <vector>

using namespace std;

int countInv(vector<int>& numvec);
int mergeInv(vector<int>& nums, vector<int>& left, vector<int>& right) {
int i=0,j=0,k=0,ans=0;
while(i<left.size() && j<right.size())
{
if(left[i] <= right[j]){
nums[k] = left[i];
i+=1;
}
else{
ans += (left.size()-i);//this is the number of inversions
nums[k] = right[j];
j+=1;
}
k+=1;
}
while(i<left.size()){
nums[k] = left[i];
i+=1;
k+=1;
}
while(j<right.size()){
nums[k] = right[j];
j+=1;
k+=1;
}
return ans;
}

int countInv(vector<int>&nums) {
int n = nums.size();
if(n==1)
return 0;
vector<int> left,right;
//Dividing the vector in two parts i.e left and right
for(int i=0;i<(n/2);i++)
left.push_back(nums[i]);
  
for(int i=(n/2);i<n;i++)
right.push_back(nums[i]);
  
return countInv(left) + countInv(right) + mergeInv(nums,left,right);
}
int main()
{
int n;
vector<int> numvec{4, 5, 6, 1, 2, 3};
n = countInv(numvec);
cout << "Number of inversions " << n << endl; // Should be 9
numvec = {1, 2, 3, 4, 5, 6};
n = countInv(numvec);
cout << "Number of inversions " << n << endl; // Should be 0
numvec = {6, 5, 4, 3, 2, 1};
n = countInv(numvec);
cout << "Number of inversions " << n << endl; // Should be 15
numvec = {0, 0, 0, 0, 0, 0};
n = countInv(numvec);
cout << "Number of inversions " << n << endl;; // Should be 0
}