Kodemonk

INVCNT – Inversion Count

Problem: 

Let A[0…n – 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. Given n and an array A your task is to find the number of inversions of A.

Read More Here


Hint: If you run two loops then solution will not accepted. Try to do sum modification to merge sort.


Code:


#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

lli merge(vector<int> &vec, int left, int mid, int right)
{
  int i = left, j = mid, k = 0;
  lli invCount = 0;
  vector<int> temp((right-left + 1));
  while ((i <= mid - 1) && (j <= right)){
    if (vec[i] <= vec[j])
      temp[k++] = vec[i++];
    else{
      temp[k++] = vec[j++];
      invCount = invCount + (mid - i);
    }
  }
  while (i <= mid - 1)
    temp[k++] = vec[i++];
  while (j <= right)
    temp[k++] = vec[j++];
 
  for (i=left,k=0; i <= right; i++)
    vec[i] = temp[k++];
 
  return invCount;
}
 

lli mMergeSort(vector<int> &vec,int left, int right)
{
  int mid;
  lli invCount = 0;
  if (right > left)
  {
    mid = (right + left)/2;
 
    invCount  = mMergeSort( vec, left, mid);
    invCount += mMergeSort(vec, mid+1, right);
 
    invCount += merge(vec, left, mid+1, right);
  }
  return invCount;
}
 
int main()
{
    int T,N;
    cin>>T;
    while(T--){
        cin>>N;
        vector<int> vec(N);
        for(int i=0;i<N;i++) cin>>vec[i];
        cout<<mMergeSort(vec,0,N-1)<<endl;
    }
  
  return 0;
}

Explanation:  As we know that merging in merge sort takes place from left to right. So if m denotes the size of the left array and a_i, b_j  are the current element in the left and right part of the array. The inversion is possible when a_i > b_j. In this case all the element after the element a_i in the left array will make inversion pair with b_j.

 

Not good at algorithms? Try this book Introduction to Algorithms

 

Share This:

Next Post

Previous Post

© 2017 Kodemonk

Theme by Anders Norén