We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Oh Ok. Yea. My own challenge, though is that it still fails in Java, despite not recreating the array on each merge. Do you have an idea what might be wrong? That's if you understand Java.
// Complete the countInversions function below.
static long countInversions(int[] arr) {
long inversionsCount = 0;
int [] lowerArray = new int [arr.length];
int [] higherArray = new int [arr.length]; //frm mid+1 to high
inversionsCount = countAndSort (arr, 0, arr.length - 1, lowerArray, higherArray);
return inversionsCount;
}
static long countAndSort(int [] arr, int low, int high, int [] lowerArray, int [] higherArray)
{
long totalCount = 0;
long count = 0;
if (low < high)
{
int mid = low + (high-low) /2;
long lowerCount = countAndSort (arr, low, mid, lowerArray, higherArray);
long higherCount = countAndSort (arr, mid+1, high, lowerArray, higherArray);
totalCount += lowerCount + higherCount + countAndSortMerge (arr, low, mid, high, lowerArray, higherArray);
}
return totalCount;
}
static long countAndSortMerge(int [] arr, int low, int mid, int high, int [] lowerArray, int [] higherArray)
{
long countInversions = 0;
for (int i=0; i< (mid-low+1);i++)
{
lowerArray[i] = arr [low+i];
}
for (int i=0; i< (high-mid);i++)
{
higherArray[i] = arr [mid+1+i];
}
int lowIndex = 0;
int highIndex = 0;
int arrIndex = low;
while (lowIndex < (mid-low+1) && highIndex < (high-mid))
{
if (lowerArray[lowIndex] <= higherArray [highIndex])
{
arr[arrIndex] = lowerArray[lowIndex];
++lowIndex;
}
else
{
arr[arrIndex] = higherArray[highIndex];
++highIndex;
countInversions += (mid-low+1 - lowIndex);
}
++arrIndex;
}
while (lowIndex < (mid-low+1))
{
arr[arrIndex] = lowerArray[lowIndex];
++lowIndex;
++arrIndex;
}
while (highIndex < (high-mid))
{
arr[arrIndex] = higherArray[highIndex];
++highIndex;
++arrIndex;
}
return countInversions;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int t = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int tItr = 0; tItr < t; tItr++) {
int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
int[] arr = new int[n];
String[] arrItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < n; i++) {
int arrItem = Integer.parseInt(arrItems[i]);
arr[i] = arrItem;
}
System.out.printf("Dataset %d \n", tItr);
long result = countInversions(arr);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedWriter.close();
scanner.close();
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
Oh Ok. Yea. My own challenge, though is that it still fails in Java, despite not recreating the array on each merge. Do you have an idea what might be wrong? That's if you understand Java.
// Complete the countInversions function below. static long countInversions(int[] arr) {