'Coding has over 700 languages', '67% of programming jobs arenâ€™t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Topics

# Count Inversions

Moderate
0/80
Average time to solve is 40m
Contributed by

## Problem statement

For a given integer array/list 'ARR' of size 'N' containing all distinct values, find the total number of 'Inversions' that may exist.

An inversion is defined for a pair of integers in the array/list when the following two conditions are met.

``````A pair ('ARR[i]', 'ARR[j]') is said to be an inversion when:

1. 'ARR[i] > 'ARR[j]'
2. 'i' < 'j'

Where 'i' and 'j' denote the indices ranging from [0, 'N').
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 <= N <= 10^5
1 <= ARR[i] <= 10^9

Where 'ARR[i]' denotes the array element at 'ith' index.

Time Limit: 1 sec
``````
Sample Input 1 :
``````3
3 2 1
``````
Sample Output 1 :
``````3
``````
Explanation of Sample Output 1:
``````We have a total of 3 pairs which satisfy the condition of inversion. (3, 2), (2, 1) and (3, 1).
``````
Sample Input 2 :
``````5
2 5 1 3 4
``````
Sample Output 2 :
``````4
``````
Explanation of Sample Output 1:
``````We have a total of 4 pairs which satisfy the condition of inversion. (2, 1), (5, 1), (5, 3) and (5, 4).
``````
Console