Citadel OA | Inversions | Citadel Online Assessment Question
A subsequence is created by deleting zero or more elements from a list while maintaining the order. For example, the subsequences of [1,2,3] are [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. An inversion is a strictly decreasing subsequence of length 3. More formally, given an array p=p[n] an inversion in the array is any time some p[i]>p[j]>p[k] and i<j<k.
Determine the number of inversions within a given array.
Relevant Citadel OA Problems:
Input & Output
Input
arr — a array of integers
Output
a long integer denoting the number of inversions in the array
Example
Input
arr = [5,3,4,2,1]
Output
7
Explanation
The array inversions are:
[5,3,2] [5,3,1] [5,4,2] [5,4,1] [5,2,1] [3,2,1] [4,2,1]
Example
Input
arr = [4,4,2,1]
Output
2
Explanation
The array inversions are:
[4,2,1] [4,2,1]
Constraints
1<=n<=50001<=arr[i]<=10^6