Given an array A of distinct numbers, how to count the number of pairs (i,j) such that
A[i] < A[j]
For example, let us consider A = [2, 1, 3]
the pairs are (1,2), (1,3), (2,3). So there are 3 pairs.
Similarly for A = [10, 6, 9, 2], there are 6 pairs
This problem was originally appeared in Codechef.
One straight forward solution is to loop through all possible pairs and count them.
But this has O(n2) time complexity.
We actually don’t need to count all the pairs because the elements are distinct.
Suppose we arrange the elements in sorted order
A = [1, 2, 3]
then the pairs are (1, 2), (1,3), (2,3)
A = [2, 6, 9, 10]
the pairs are (2, 6), (2,9), (2,10), (6, 9), (6, 10), (9,10)
If there are n elements in an array, there will be n*(n-1) pairs. Since the all the elements are unique, half of them satisfies the given property.
So the answer will be n*(n-1)/2