Interview Question
Country: India
I guess it means an anomaly in ordering.
e.g 2,7,5,6,9,8
For increasing order, there are two inversions <7,5> and <9,8>
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;
}
/* 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
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)
Hint:
- mrb March 12, 2012Try modifying merge sort's merge procedure, to keep track of the count.