Problem Title: Count Inversions

Problem Description

• Given an array of integers. Find the Inversion Count in the array. Two array elements arr[i] and arr[j] form an inversion if arr[i] > arr[j] and i < j.
• Inversion Count: For an array, inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted then the inversion count is 0. If an array is sorted in the reverse order then the inversion count is the maximum.

Examples:

Input: n = 5, arr[] = {2, 4, 1, 3, 5}
Output: 3
Explanation: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).        

Example 2:

Input: n = 5, arr[] = {2, 3, 4, 5, 6}
Output: 0
Explanation: As the sequence is already sorted so there is no inversion count.        

Example 3:

Input: n = 3, arr[] = {10, 10, 10}
Output: 0
Explanation: As all the elements of array are same, so there is no inversion count.        

• Expected Time Complexity: O(nLogn).
• Expected Auxiliary Space: O(n).

Constraints:

• 1 ≤ n ≤ 5*105
• 1 ≤ arr[i] ≤ 1018

Java Code

class Solution {

    public static long merge(long arr[], int si, int mid, int ei) {
        long[] merged = new long[ei - si + 1];
        int first = si;
        int second = mid + 1;
        int x = 0;
        long count = 0;
        
        while (first <= mid && second <= ei) {
            if (arr[first] <= arr[second]) {
                merged[x++] = arr[first++];
            } else {
                merged[x++] = arr[second++];
                count += (mid - first + 1);
            }
        }
        
        while (first <= mid) {
            merged[x++] = arr[first++];
        }
        
        while (second <= ei) {
            merged[x++] = arr[second++];
        }
        
        for (int i = 0, j = si; i < merged.length; i++, j++) {
            arr[j] = merged[i];
        }
        
        return count;
    }
    
    public static long divide(long arr[], int si, int ei) {
        long count = 0;
        if (si < ei) {
            int mid = si + (ei - si) / 2;
            count += divide(arr, si, mid);
            count += divide(arr, mid + 1, ei);
            count += merge(arr, si, mid, ei);
        }
        return count;
    }
    
    static long inversionCount(long arr[], long N) {
        return divide(arr, 0, (int) N - 1);
    }
}        

Explanation

• The problem can be solved using the merge sort algorithm. The idea is to count the number of inversions while merging the two halves of the array.

1. The merge function is used to merge the two halves of the array and count the number of inversions.
2. The divide function is used to divide the array into two halves and count the number of inversions.
3. The inversionCount function is used to call the divide function and return the total number of inversions in the array.
4. The time complexity of the solution is O(nLogn) and the space complexity is O(n).