Counting pairs in array | Letuscode
Given an array A of distinct numbers, how to count the number of pairs
For example, let us consider
the pairs are
Similarly for
then the pairs are
the pairs are
Read full article from Counting pairs in array | Letuscode
Given an array A of distinct numbers, how to count the number of pairs
(i,j) such thatA[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
We actually don’t need to count all the pairs because the elements are distinct.
Suppose we arrange the elements in sorted order
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