Given an array of positive integers. The task is to find an inversion count of the array.
Inversion Count: For an array, inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted then the inversion count is 0. If the array is sorted in the reverse order that inversion count is the maximum.
Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.
Output:
Print the inversion count of the array.
Example:
Input:
1
5
2 4 1 3 5
Output:
3
Explanation:
Testcase 1: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).
#include <iostream>
using namespace std;
void merg(int left[],int right[],int l,int r,int a[],long int & inver)
{
int i=0,j=0,k=0;
while(i<l&&j<r)//running loop while i and j less than l and r respectivily
{
if(left[i]<=right[j])
{
a[k++]=left[i++];
}else{
a[k++]=right[j++];
//when a[j] is smaller than a[i] that i to l all are greater so these create inversion
inver+=l-i;
}
}
while(i<l)
{
a[k++]=left[i++];
}
while(j<r){
a[k++]=right[j++];
}
}
void mergsort(int a[],int n,long int &inver)
{
// n less than 2 then return bcz one element si not splited
if(n<2)return;
int mid=n/2;
// creating left array of size of mid and assign value from 0 to mid-1
int left[mid];
// creating right array of size of n-mid and assign from mid to n-1
int right[n-mid];
for(int i=0;i<mid;++i)
left[i]=a[i];
for(int i=mid;i<n;++i)
right[i-mid]=a[i];
//spliting the array upto 1 size
mergsort(left,mid,inver);//call mergsort with left with its size
mergsort(right,n-mid,inver);//call mergsort with right with its size
merg(left,right,mid,n-mid,a,inver);//call merg all array from size 1,2,4..(2^k=n)
}
int main() {
//code
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;++i)
{
cin>>a[i];
}
long int inver=0;
mergsort(a,n,inver);
cout<<inver<<endl;
}
return 0;
}
