Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Last Updated: 10 Jan, 2017

Count Inversions

Asked in companies

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').
Input format :
The first line of input contains an integer 'N', denoting the size of the array.

The second line of input contains 'N' integers separated by a single space, denoting the elements of the array 'ARR'.
Output format :
Print a single line containing a single integer that denotes the total count of inversions in the input array.
You are not required to print anything, it has been already taken care of. Just implement the given function.  
Constraints :
1 <= N <= 10^5 
1 <= ARR[i] <= 10^9

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

Time Limit: 1 sec


01 Approach

The steps are as follows:


  1. Initialize a ‘COUNT’ with 0 to keep track of the number of inversions
  2. Iterate over every element in the array in a linear fashion starting from 0.
  3. For every element, check all the elements ahead of the current element and check the condition.
    1. If the condition satisfies, increase the ‘COUNT’ by 1.
    2. Otherwise, move to the next iteration.
  4. Return the ‘COUNT’.