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:

• Triplets
• Ways to Sum
• Consecutive Sum
• Disk Space Analysis
• Do They Belong?
• Global Maximum
• Initial Public Offering
• Inversions
• Portfolio Balances
• Prime Factor Visitation
• Profit Targets
• Sprint Training
• Throttling Gateway
• Birthday Card Collection

Input

• arr: a array of integers

Output

a long integer denoting the number of inversions in the array

Examples

Example 1:

Input:

1arr = [5,3,4,2,1]

Output: 7

Explanation:

The array inversions are:

1[5,3,2]
2[5,3,1]
3[5,4,2]
4[5,4,1]
5[5,2,1]
6[3,2,1]
7[4,2,1]

Example 2:

Input:

1arr = [4,4,2,1]

Output: 2

Explanation:

The array inversions are:

1[4,2,1]
2[4,2,1]

Constraints

• 1<=n<=5000
• 1<=arr[i]<=10^6

Try it yourself

Solution