CareerCup

Hint:
Try modifying merge sort's merge procedure, to keep track of the count.

Use merge sort.. count inversions when you put element from right array to left ..

Wat u mean by inversion?

Following code wil give the number of inversions in a sequence of n mumbers

#include<iostream>
#include<iomanip>
using namespace std;
long long int mergeArrays(int arr[],int beg,int mid,int end)
{
	int i,j,*temp,k=0,p=0;
	long long int count=0;
	temp=new int[end-beg+1];
	i=beg;j=mid+1;
	while(i<=mid && j<=end){
		while(j<=end && arr[i] > arr[j]){temp[k++]=arr[j++];++p;}
		count+=p;
		temp[k++]=arr[i++];
	}
	while(j<=end){
		temp[k++]=arr[j++];
	}
	while(i<=mid){	temp[k++]=arr[i++]; count+=(end-mid);}
	for(i=0;i<k;i++)	arr[beg+i]=temp[i];
return count;
}

long long int countInversion(int arr[],int beg,int end){
	int mid;
	long long int noi=0;
	if(beg<end){
		mid=(beg+end)/2;
		noi=countInversion(arr,beg,mid);
		noi+=countInversion(arr,mid+1,end);
		noi+=mergeArrays(arr,beg,mid,end);
	}
	return noi;
}
int main()
{
	int i, a[100000];
	for(i=0;i<100000;i++)	cin>>a[i];
	cout<<countInversion(a,0,99999)<<endl;

return 0;
}

#include <iostream>
#include <iomanip>
#include <stdio.h>

using namespace std;

const int MAXN = 100000;
int numbers[MAXN];
long result;

//read the file to numbers
void num_read()
{
freopen("integerArray.txt","r",stdin);
for (int i=0;i<MAXN;i++)
cin >> numbers[i];
}

//merge fuction
void merge(int* input, int low, int high)
{
int mid = ((low + high) / 2);
int i = 0;
int left = low;
int right = mid + 1;

// Temp array
int t=high - low + 1;
int temp[t];


while(left <= mid && right <= high)
{
if(input[left] < input[right])
temp[i++] = input[left++];
else
{
temp[i++] = input[right++];
result += (mid - left + 1);
}
}

while(left <= mid)
temp[i++] = input[left++];

while(right <= high)
temp[i++] = input[right++];

for(i = low; i < high + 1; ++i)
input[i] = temp[i - low];

}


//merge sort function
void merge_sort(int* input, int low, int high)
{
if ( low < high )
{
int mid = ((low + high) / 2);
merge_sort(input, low, mid);
merge_sort(input, mid + 1, high);
merge(input, low, high);
}

}


int main()
{
num_read();
merge_sort(numbers, 0, MAXN-1);
cout<<result<<endl;

return 0;
}

#include <iostream>
#include <iomanip>
#include <stdio.h>

using namespace std;

const int MAXN = 100000;
int numbers[MAXN];
long result;

//read the file to numbers
void num_read()
{
freopen("integerArray.txt","r",stdin);
for (int i=0;i<MAXN;i++)
cin >> numbers[i];
}

//merge fuction
void merge(int* input, int low, int high)
{
int mid = ((low + high) / 2);
int i = 0;
int left = low;
int right = mid + 1;

// Temp array
int t=high - low + 1;
int temp[t];


while(left <= mid && right <= high)
{
if(input[left] < input[right])
temp[i++] = input[left++];
else
{
temp[i++] = input[right++];
result += (mid - left + 1);
}
}

while(left <= mid)
temp[i++] = input[left++];

while(right <= high)
temp[i++] = input[right++];

for(i = low; i < high + 1; ++i)
input[i] = temp[i - low];

}


//merge sort function
void merge_sort(int* input, int low, int high)
{
if ( low < high )
{
int mid = ((low + high) / 2);
merge_sort(input, low, mid);
merge_sort(input, mid + 1, high);
merge(input, low, high);
}

}


int main()
{
num_read();
merge_sort(numbers, 0, MAXN-1);
cout<<result<<endl;

return 0;
}

All the above codes are wrong.

3

/* Include Header Files
*/
#include "stdio.h"
#include "stdlib.h"

/* Include Pre-processor directives
*/
#define N 100000

/* Function Proto-type
*/
void partition(long int *data, int first, int last);
void merge(long int *data, int first, int mid, int last);

/* Global Variable
*/
unsigned int counter = 0;

int main()
{
/* Declaring and initializing variables
*/
long int data[N] = {0};
int multiplying_factor = 10;
char c = '\0';
char d = 0;
long int sum = 0;
int indexcount = 0;

/* FILE READ OPERATION, USER CAN USE THEIR OWN FILE OPERATION
* IF NEEDED OR FOR SMALL ARRAY SIZE INITIALIZE THE VALUE
* OF ARRAY DURING DECLARATION
*/
/* Open file in directory
*/
FILE *fp = fopen("F:/IntegerArray.txt", "r");


/* Read till end of file
*/
while (c != EOF)
{
/* Reading file by character
*/
c = fgetc(fp);

if (c != '\n')
{
d = atoi(&c);

sum = (sum * multiplying_factor) + d;
}
else
{
/* Filling data in array
*/
data[indexcount] = sum;
indexcount = indexcount + 1;
sum = 0;
}
}

fclose(fp);

partition(data, 0, N - 1);

printf("\nCounter = %u \n", counter);

return 0;
}


void partition(long int *data, int left, int right)
{
int middle = (left + right) / 2;

if (left < right)
{
partition(data, left, middle);
partition(data, middle + 1, right);
merge(data, left, middle, right);
}

}

void merge(long int *data, int left, int middle, int right)
{
/* Declaring and initializing variables
*/
int Nleft = middle - left + 1;
int Nright = right - middle;
long int left_data[N] = {0};
long int right_data[N] = {0};
int index = 0;
int index_l = 0;
int index_r = 0;

/* Initialize left_data array
*/
for(index = 0; index < Nleft; index++)
{
left_data[index] = data[left + index];
}
/* Initialize right_data array
*/
for (index = 0; index < Nright; index++)
{
right_data[index] = data[middle + 1 + index];
}

index = left;

while (index_l < Nleft && index_r < Nright)
{
if (left_data[index_l] < right_data[index_r])
{
data[index] = left_data[index_l];
index_l++;

}
else
{
data[index] = right_data[index_r];
index_r++;

/* Updating counter
*/
counter = counter + (Nleft - index_l);
}

index++;
}

while(index_l < Nleft)
{
data[index] = left_data[index_l];
index++;
index_l++;
}

while(index_r < Nright)
{
data[index] = right_data[index_r];
index++;
index_r++;
}


}

#include <iostream>
using namespace std;
long long int merge(long long int arr[],long long int temp[],long long int left,long long int mid,long long int right){
long long int i, j, k;
long long int count = 0;
i = left; //i to locate first array location
j = mid; //i to locate second array location
k = left; //i to locate merged array location
while ((i <= mid - 1) && (j <= right)){
if (arr[i] <= arr[j]){ //when left item is less than right item
temp[k++] = arr[i++];
}
else{
temp[k++] = arr[j++];
count += (mid - i); //find how many convertion is performed
}
}
while (i <= mid - 1) //if first list has remaining item, add them in the list
temp[k++] = arr[i++];
while (j <= right) //if second list has remaining item, add them in the list
temp[k++] = arr[j++];
for (i=left; i <= right; i++)
arr[i] = temp[i]; //store temp Array to main array
return count;
}
long long int mergeSort(long long int arr[],long long int temp[],long long int left,long long int right){
long long int mid, count = 0;
if (right > left){
mid = (right + left)/2; //find mid index of the array
count = mergeSort(arr, temp, left, mid); //merge sort left sub array
count += mergeSort(arr, temp, mid+1, right); //merge sort right sub array
count += merge(arr, temp, left, mid+1, right); //merge two sub arrays
}
return count;
}
long long int arrInversion(long long int arr[],long long int n){
long long int temp[n];
return mergeSort(arr, temp, 0, n - 1);
}
int main()
{ long long int n;
cout<<"Enter value of n ="<<endl;
cin>>n;
long long int arr[n];
cout<<"Enter elements in array ="<<endl;
for(long long int o=0;o<n;o++)
{
cin>>arr[o];
}

cout << "Number of inversions are "<< arrInversion(arr, n);
}



Answer is 2407905288

2407905288

tq for the answer

def count_inversions(arr):
if len(arr) <= 1:
return arr, 0

mid = len(arr) // 2
left_half, left_count = count_inversions(arr[:mid])
right_half, right_count = count_inversions(arr[mid:])
merged_arr, merge_count = merge_and_count(left_half, right_half)

return merged_arr, left_count + right_count + merge_count

def merge_and_count(left, right):
result = []
count = 0
i = j = 0

while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
count += len(left) - i
j += 1

result.extend(left[i:])
result.extend(right[j:])

return result, count

# Read integers from the file
with open("IntegerArray.txt", "r") as file:
integers = [int(line.strip()) for line in file]

# Count inversions
sorted_integers, inversion_count = count_inversions(integers)

# Print the number of inversions
print(inversion_count)

Surely this can be done in O(n) time by looking at each line, and counting the number of cases where the line number != value on that line.
The number of inversions is half this number.