We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Interview Preparation Kit
  3. Sorting
  4. Merge Sort: Counting Inversions

Merge Sort: Counting Inversions

Problem
Submissions
Leaderboard
Discussions
Editorial

In an array, , the elements at indices and (where ) form an inversion if . In other words, inverted elements and are considered to be "out of order". To correct an inversion, we can swap adjacent elements.

Example

To sort the array, we must perform the following two swaps to correct the inversions:

The sort has two inversions: and .

Given an array , return the number of inversions to sort the array.

Function Description

Complete the function countInversions in the editor below.

countInversions has the following parameter(s):

  • int arr[n]: an array of integers to sort

Returns

  • int: the number of inversions

Input Format

The first line contains an integer, , the number of datasets.

Each of the next pairs of lines is as follows:

  1. The first line contains an integer, , the number of elements in .
  2. The second line contains space-separated integers, .

Constraints

Sample Input

STDIN       Function
-----       --------
2           d = 2
5           arr[] size n = 5 for the first dataset
1 1 1 2 2   arr = [1, 1, 1, 2, 2]
5           arr[] size n = 5 for the second dataset     
2 1 3 1 2   arr = [2, 1, 3, 1, 2]

Sample Output

0  
4   

Explanation

We sort the following datasets:

  1. is already sorted, so there are no inversions for us to correct.

We performed a total of swaps to correct inversions.

Author

HackerRank

Difficulty

Hard

Max Score

45

Submitted By

62701

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy