Merge Sort

Question - 1

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example:

Input: arr[] = {8, 4, 2, 1}
Output: 6

Explanation: Given array has six inversions:
(8,4), (4,2),(8,2), (8,1), (4,1), (2,1).


Input: arr[] = {3, 1, 2}
Output: 2

Explanation: Given array has two inversions:
(3, 1), (3, 2) 

class GFG {
    // Some Question
    // Why this works ?
    // 1) When we are merging the sorted parts, then we have already taken care of
    // inversions within each part, therefore we only need to take care of
    // inversions with the other part
    // 2) We need to understand that when we compare i & j in sorted order, you
    // might think that we need inversion in unsorted array
    // But remember that 1st part is sorted within itself that means that value at
    // index i, will be before j value in the original array aswell
    public static long merge(int[] arr, int start, int end) {
        int mid = start + (end - start) / 2;
        int[] holderArr = new int[end - start + 1];
        int pointer1 = start, pointer2 = mid + 1, index = 0;
        long inversions = 0;
        while (pointer1 <= mid && pointer2 <= end) {
            if (arr[pointer1] <= arr[pointer2])
                holderArr[index++] = arr[pointer1++];
            // If arr[i] > arr[j], then all the elements will be > arr[j]
            // because it is sorted array
            else {
                inversions += (mid - pointer1 + 1);
                holderArr[index++] = arr[pointer2++];
            }
        }
        while (pointer1 <= mid)
            holderArr[index++] = arr[pointer1++];
        while (pointer2 <= end)
            holderArr[index++] = arr[pointer2++];
        // Copying the changes into original array
        for (int i = start; i <= end; i++)
            arr[i] = holderArr[i - start];
        return inversions;
    }

    public static long mergeSort(int[] arr, int start, int end) {
        if (start >= end)
            return 0L;
        int mid = start + (end - start) / 2;
        long leftInversions = mergeSort(arr, start, mid);
        long rightInversions = mergeSort(arr, mid + 1, end);

        return leftInversions + rightInversions + merge(arr, start, end);
    }

    public static long countInversions(int[] arr) {
        return mergeSort(arr, 0, arr.length - 1);
    }
}

Question - 2

Once detective Saikat was solving a murder case. While going to the crime scene he took the stairs and saw that a number is written on every stair. He found it suspicious and decides to remember all the numbers that he has seen till now. While remembering the numbers he found that he can find some pattern in those numbers. So he decides that for each number on the stairs he will note down the sum of all the numbers previously seen on the stairs which are smaller than the present number. Calculate the sum of all the numbers written on his notes diary.

Answer may not fit in integer . You have to take long.

Input

First line gives T, number of test cases.

2T lines follow.

First line gives you the number of stairs N

Next line gives you N numbers written on the stairs.

Output

For each test case output one line giving the final sum for each test case.

Output

For each test case output one line giving the final sum for each test case.

Constraints

T<=10

1<=N<=10^5

All numbers will be between 0 and 10^6.

Sample Input:

1
5
1 5 3 6 4

Sample Output:

15

Explanation:

For the first number, the contribution to the sum is 0.
For the second number, the contribution to the sum is 1.
For the third number, the contribution to the sum is 1.
For the fourth number, the contribution to the sum is 9 (1+5+3).
For the fifth number, the contribution to the sum is 4 (1+3).
Hence the sum is 15 (0+1+1+9+4).

public class Main {
    public static long merge(int A[], int left, int right) {
        int mid = left + (right - left) / 2;
        int pointer1 = left, pointer2 = mid + 1, index = 0;
        int temp[] = new int[right - left + 1];
        long count = 0;
        while (pointer1 <= mid && pointer2 <= right) {
            // If arr[p1] is smaller that arr[p2], then arr[p1] will be smaller than all the
            // elements following arr[p2]
            if (A[pointer1] < A[pointer2]) {
                count += A[pointer1] * (right - pointer2 + 1);
                temp[index++] = A[pointer1++];
            } else
                temp[index++] = A[pointer2++];
        }
        while (pointer1 <= mid)
            temp[index++] = A[pointer1++];
        while (pointer2 <= right)
            temp[index++] = A[pointer2++];
        for (int i = left; i <= right; i++)
            A[i] = temp[i - left];
        return count;
    }

    public static long mergeSort(int arr[], int left, int right) {
        if (left >= right)
            return 0L;
        int mid = left + (right - left) / 2;
        long leftSum = mergeSort(arr, left, mid);
        long rightSum = mergeSort(arr, mid + 1, right);
        long mergeSum = merge(arr, left, right);
        return (mergeSum + leftSum + rightSum);
    }

    public static long requiredSum(int[] arr, int n) {
        return mergeSort(arr, 0, n - 1);
    }
}

Question - 3

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note: A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:

Input: nums = [-2,5,-1], lower = -2, upper = 2,
Output: 3 
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.

class Solution {
    int lower, upper;

    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] prefixSum = new long[nums.length + 1];
        this.lower = lower;
        this.upper = upper;
        // PrefixSum[i] -> Sum of first i elements
        for (int i = 1; i <= nums.length; i++)
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        return mergeSort(prefixSum, 0, prefixSum.length - 1);
    }

    private int mergeSort(long[] prefixSum, int start, int end) {
        if (start >= end)
            return 0;
        int mid = start + (end - start) / 2;
        // The pairs in the left half and the pairs in the 
        // right half get counted in the recursive calls.
        int leftAns = mergeSort(prefixSum, start, mid);
        int rightAns = mergeSort(prefixSum, mid + 1, end);
        // We just need to also count the pairs that use both halves.
        return leftAns + rightAns + merge(prefixSum, start, end);
    }

    private int merge(long[] prefixSum, int start, int end) {
        int ans = 0, mid = start + (end - start) / 2;
        long[] temp = new long[end - start + 1];
        int pointer1 = start, pointer2 = mid + 1, index = 0;
        int left = mid + 1, right = mid + 1;
        // O(N), because "left" & "right" variables only move right
        while (pointer1 <= mid) {
            // We find a limit, such that we just enter "lower" limit
            while (left <= end && prefixSum[left] - prefixSum[pointer1] < lower)
                left++;
            // We find a limit, such that we just get out of "upper" limit
            while (right <= end && prefixSum[right] - prefixSum[pointer1] <= upper)
                right++;
            // Normal merging process
            while (pointer2 <= end && prefixSum[pointer2] < prefixSum[pointer1])
                temp[index++] = prefixSum[pointer2++];
            temp[index++] = prefixSum[pointer1++];
            // Answer will be [L,R], L is shown by pointer1, & 
            // R is shown by all the values in between [left,right)
            ans += right - left;
        }
        while (pointer2 <= end)
            temp[index++] = prefixSum[pointer2++];
        for (int i = start; i <= end; i++)
            prefixSum[i] = temp[i - start];
        return ans;
    }
}

Question - 4

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

class Solution {
    static class Pair {
        int val, i;

        Pair(int val, int index) {
            this.val = val;
            this.i = index;
        }
    }

    List<Integer> ans;

    public List<Integer> countSmaller(int[] nums) {
        // Creating answer array
        ans = new ArrayList<>();
        Pair[] arr = new Pair[nums.length];
        for (int i = 0; i < arr.length; i++) {
            ans.add(0);
            arr[i] = new Pair(nums[i], i);
        }
        mergeSort(arr, 0, nums.length - 1);
        return ans;
    }

    public void mergeSort(Pair[] arr, int start, int end) {
        if (start >= end)
            return;
        int mid = start + (end - start) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, end);
    }

    public void merge(Pair[] arr, int start, int end) {
        int mid = start + (end - start) / 2;
        Pair[] temp = new Pair[end - start + 1];
        int index = 0, pointer1 = start, pointer2 = mid + 1;
        int limit = mid + 1;
        while (pointer1 <= mid) {
            // For every element in the left part, we are finding count of 
            // elements in right part < element
            while (limit <= end && arr[limit].val < arr[pointer1].val)
                limit++;
            ans.set(arr[pointer1].i, ans.get(arr[pointer1].i) + limit - (mid + 1));
            // Merge process
            while (pointer2 <= end && arr[pointer2].val < arr[pointer1].val)
                temp[index++] = arr[pointer2++];
            temp[index++] = arr[pointer1++];
        }
        while (pointer2 <= end)
            temp[index++] = arr[pointer2++];
        for (int i = start; i <= end; i++)
            arr[i] = temp[i - start];
    }
}

Question - 5

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

Input: [2,4,3,5,1]
Output: 3

Note:

1. The length of the given array will not exceed 50,000.

2. All the numbers in the input array are in the range of 32-bit integer.

class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    public int mergeSort(int[] nums, int start, int end) {
        if (start >= end)
            return 0;
        int mid = start + (end - start) / 2;
        int leftAns = mergeSort(nums, start, mid);
        int rightAns = mergeSort(nums, mid + 1, end);
        return leftAns + rightAns + merge(nums, start, end);
    }

    public int merge(int[] nums, int start, int end) {
        int mid = start + (end - start) / 2;
        int p1 = start, p2 = mid + 1;
        int pointer = mid + 1, index = 0, count = 0;
        int[] temp = new int[end - start + 1];
        while (p1 <= mid) {
            // All the elements behind pointer, are satisfying the equation with "p1"
            while (pointer <= end && 2L * nums[pointer] < (long) nums[p1])
                pointer++;
            count += pointer - (mid + 1);
            while (p2 <= end && nums[p2] < nums[p1])
                temp[index++] = nums[p2++];
            temp[index++] = nums[p1++];
        }
        while (p2 <= end)
            temp[index++] = nums[p2++];
        for (int i = start; i <= end; i++)
            nums[i] = temp[i - start];
        return count;
    }
}