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
4d

Count the total number of inversions in an integer array.

  • Iterate through the array and for each element, check how many elements to its right are smaller than it.

  • Use a merge sort based approach to eff...read more

Help your peers!
Add answer anonymously...
HSBC Group Software Engineer Trainee Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
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

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter