
Inversion Count Problem
Given an integer array ARR
of size N
with all distinct values, determine the total number of 'Inversions' that exist.
Explanation:
An inversion is a pair of indices (i, j)
such that:
ARR[i] > ARR[j]
i < j
Input:
N
ARR[0] ARR[1] ... ARR[N-1]
Output:
The total count of inversions in the array.
Example:
Input:
5
2 4 1 3 5
Output:
3
Explanation:
There are 3 inversions in the array: (2, 1), (4, 1), and (4, 3).
Constraints:
1 <= N <= 10^5
1 <= ARR[i] <= 10^9
Note:
You do not need to print anything; just implement the function that returns the count of inversions.

AnswerBot
5d

Count the total number of inversions in an integer array.
Use a modified merge sort algorithm to count the inversions.
Keep track of the count of inversions while merging the subarrays.
The time complexi...read more

Help your peers!
Add answer anonymously...
Top Amazon Software Developer interview questions & answers
Popular interview questions of Software Developer
Top HR questions asked in Amazon Software Developer
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app