Hi,
The below program is used to count the no of inversions in an array.The program works fine for small input but for large input it fails as there is overflow.
The variable inv_count which counts the no of inversion is declared to be long long int but it down castes to int and after (2,147,483,647) it moves to the negative side giving the wrong output. Can someone help me in setting the proper range of the variabel inv_count.
Here is my code:
#include<stdio.h>
#include<iostream>
#include<fstream>
#include <bits/stdc++.h>
long long getInvCount(int arr[], long n)
{
long long inv_count = 0LL;
for (long i = 0; i < n - 1; i++)
{
for (long j = i+1; j < n; j++)
{
if (arr[i] > arr[j])
inv_count++ ;
}
}
return inv_count;
}
int main(int argv, char** args)
{
int arr [100000];
std::fstream numfile("Text.txt", std::ios_base::in);
long val;
long count = 0;
while (numfile >> val && count < 100000)
{
arr[count++] = val;
}
numfile.close();
printf(" Number of inversions are %lld \n", getInvCount(arr,count));
getchar();
return 0;
}