HackerRank Merge Sort: Counting Inversions problem solution

In this HackerRank Merge Sort: Counting Inversion Interview preparation kit problem In an array, arr, the elements at indices i and j (where i < j) form an inversion if arr[i] > arr[j]. In other words, inverted elements arr[i] and arr[j] are considered to be “out of order”.

Problem solution in Python programming.

def merge(a, l, m, h):
    c = []
    i = l
    j = m + 1
    s = 0
    
    while i <= m and j <= h:
        if a[i] > a[j]:
            # there is an inversion
            s += (m - i + 1)
            c.append(a[j])
            j += 1
        else:
            c.append(a[i])
            i += 1
            
    # Adding remaning numbers
    while i <= m:
        c.append(a[i])
        i += 1
    while j <= h:
        c.append(a[j])
        j += 1
        
    
    a[l: h + 1] = c
    
    return s
            

def count(a, l, h):
    if l >= h:
        return 0
    #print(l, h)
    m = l + (h - l) // 2
    s = 0
    s += count(a, l, m)
    s += count(a, m + 1, h)
    
    s += merge(a, l, m, h)
    return s

def count_inversions(a):
    return count(a, 0, len(a) - 1)

t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    arr = list(map(int, input().strip().split(' ')))
    print(count_inversions(arr))

Problem solution in Java Programming.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    private static long mergeSortCount(int[] a, int[] aux, int from, int to) {
        if (from >= to) { return 0; }
        int mid = (from + to) >>> 1;
        long count = 0L;
        count += mergeSortCount(a, aux, from, mid);
        count += mergeSortCount(a, aux, mid + 1, to);
        count += merge(a, aux, from, mid, to);
        return count;
    }
    
    private static long merge(int[] a, int[] aux, int from, int mid, int to) {
        System.arraycopy(a, from, aux, from, to - from + 1);
        long count = 0L;
        int i = from, j = mid + 1;
        for (int k = from; k <= to; k++) {
            if (i > mid) {
                a[k] = aux[j++];    
            } else if (j > to) {
                a[k] = aux[i++];
            } else if (aux[j] < aux[i]) {
                a[k] = aux[j++];
                count += mid - i + 1;
            } else {
                a[k] = aux[i++];
            }
        }
        return count;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            int n = in.nextInt();
            int arr[] = new int[n];
            for(int arr_i=0; arr_i < n; arr_i++){
                arr[arr_i] = in.nextInt();
            }
            System.out.println(mergeSortCount(arr, new int[n], 0, n - 1));
        }
    }
}

Problem solution in C++ programming.

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;


uint64_t insertionSort(vector<int> &ar, int low, int high) {
    if (high - low < 2) {
        return 0;
    }

    int mid = (low + high) / 2;
    uint64_t count;
    
    count = insertionSort(ar, low, mid);
    count += insertionSort(ar, mid, high);

    vector<int> aux(ar.begin() + low, ar.begin() + mid);
    int walk = mid;
    int cur = low;
    int i = 0;
    while ((i < aux.size()) && (walk < high)) {
        if (ar[walk] < aux[i]) {
            ar[cur++] = ar[walk++];
            count += (walk - cur);
        } else {
            ar[cur++] = aux[i++];
        }
    }

    while(i < aux.size()) {
        ar[cur++] = aux[i++];
    }

#if 0
    for (int i = low + 1; i < high; i++) {
        int cur = ar[i];
        int j;
        for (j = i - 1; (j >= low) && (cur < ar[j]); j--) {
            ar[j + 1] = ar[j];
            count++;
        }
        
        ar[j+1] = cur;
    }
#endif
    
    return count;
}



int mergeSort(vector<int> & a) {
    int count = 0;
    
    if (a.size() >= 2) {
        vector<int> first(a.begin(), a.begin() + a.size() / 2);
        vector<int> second(a.begin() + a.size() / 2, a.end());
        
        count += mergeSort(first);
        count += mergeSort(second);
        //cout << first.size() << ":" << second.size() << ":" << count << endl;
        
        int i = 0, j = 0;
        while (i < first.size() && j < second.size()) {
            if (first[i] <= second[j]) {
                a[i + j] = first[i];
                i++;
            } else {
                a[i + j] = second[j];
                count += (first.size() - i);
                //cout << count << "-" << (first.size() - i) << endl;
                j++;
            }
        }

        while (i < first.size()) {
            a[i + j] = first[i];
            i++;
        }

        while (j < second.size()) {
            a[i + j] = second[j];
            j++;
        }
    }
    
    return count;
}

uint64_t count_inversions(vector<int> &a) {
#if 0
    int count = 0;
    
    for (int i = 1; i < a.size(); i++) {
        if (a[i] < a[i-1]) {
            int idx = i;
            while ((idx != 0)  && (a[idx] < a[idx - 1])) {
                swap(a[idx], a[idx - 1]);
                idx--;
                count++;
            }
        }
    }
#endif    
    return insertionSort(a, 0, a.size());
}

int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        cin >> n;
        vector<int> arr(n);
        for(int arr_i = 0;arr_i < n;arr_i++){
           cin >> arr[arr_i];
        }
        cout << count_inversions(arr) << endl;
    }
    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <stdint.h>
#include <string.h>

#define RUN_TEST_CASES(VAR) int VAR##_total; scanf("%d", & VAR##_total); 
	for(int VAR=1; VAR<=VAR##_total; ++VAR)

typedef unsigned long long ull;

ull merge(int *a, const int first, const int last)
{
	if (last - first == 1)
		return 0;

	if (last - first == 2)
	{
		if (a[first + 1] < a[first])
		{
			int tmp = a[first];
			a[first] = a[first + 1];
			a[first + 1] = tmp;

			return 1;
		}

		return 0;
	}

	int m = first + (last - first) / 2;

	ull inversions = merge(a, first, m);
	inversions += merge(a, m, last);

	int lo = first, hi = m;
	int t = first;

	static int temp[100001];

	while (lo < m && hi < last)
	{
		if (a[lo] <= a[hi])
		{
			temp[t++] = a[lo++];
			continue;
		}

		temp[t++] = a[hi++];
		inversions += m - lo;
	}

	while (lo < m) temp[t++] = a[lo++];
	while (hi < last) temp[t++] = a[hi++];

	for (int j = first; j < last; ++j)
		a[j] = temp[j];

	return inversions;
}

int main()
{
#ifdef _DEBUG
	char FNAME[250];
	strcpy(FNAME, __FILE__);
	strcpy(strchr(FNAME, '.'), ".txt");
	freopen(FNAME, "rt", stdin);
#endif

	RUN_TEST_CASES(test_case)
	{
		int a[100001];

		int n;
		scanf("%d", &n);
		for (int j = 0; j < n; ++j)
			scanf("%d", &a[j]);

		printf("%llun", merge(a, 0, n));
	}
}

Problem solution in JavaScript programming.

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.replace(/s*$/, '')
        .split('n')
        .map(str => str.replace(/s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

function countInversions(arr) {
    return sortAndCount(arr);
}

function sortAndCount(arr) {
    if (arr.length < 2) {
        return 0;
    }

    var mid = Math.floor(arr.length / 2);
    var left = arr.slice(0, mid);
    var right = arr.slice(mid);

    return sortAndCount(left) + sortAndCount(right) + mergeSortAndCount(arr, left, right);
}

function mergeSortAndCount(arr, left, right) {
    var i = 0, leftIndex = 0, rightIndex = 0, inversions = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] <= right[rightIndex]) {
            arr[i] = left[leftIndex];
            leftIndex++;
        } else {
            arr[i] = right[rightIndex];
            rightIndex++;
            inversions += (left.length - leftIndex);
        }

        i++;
    }

    while (leftIndex < left.length) {
        arr[i] = left[leftIndex];
        leftIndex++;
        i++;
    }

    while (rightIndex < right.length) {
        arr[i] = right[rightIndex];
        rightIndex++;
        i++;
    }

    return inversions;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const n = parseInt(readLine(), 10);

        const arr = readLine().split(' ').map(arrTemp => parseInt(arrTemp, 10));

        const result = countInversions(arr);

        ws.write(result + 'n');
    }

    ws.end();
}