Count Inversions
Hard Problems: Merge & Intervals DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Counting inversions in an array using Merge Sort, Arrays, Merge Sort, Divide and Conquer, Time Complexity, Space Complexity, Loops, Conditional Statements, Inversion Count, complexity analysis, brute force, sorting algorithms, divide and conquer, array algorithms, Array Inversions.
Problem Statement: Given an array A of N integers, find the total number of inversions. An inversion is a pair of indices (i, j) such that i < j and A[i] A[j]. Input Format: The first line contains an integer N, representing the size of the array. The second line contains N space separated integers, representing the elements of the array A. Output Format: Print a single integer, the total number of inversions in the array. Examples: Example 1: Input: 5 1 2 3 4 5 Output: 0 Explanation: We have a sorted array. For any i < j, it will always be A[i] <= A[j]. Hence, there are no inversions. Example 2: Input: 5 5 4 3 2 1 Output: 10 Explanation: We have a reverse sorted array. For any i < j, it will always be A[i] A[j]. The total number of inversions for a reverse sorted array of size N is N (N 1) / 2. For N=5, this is 5 4 / 2 = 10. Example 3: Input: 5 5 3 2 1 4 Output: 7 Explanation: The inversion pairs are: (5,1), (5,3), (5,2), (5,4), (3,2), (3,1), (2,1). Total 7 inversions.