Problem:
You are given an array of N numbers. You are to find the number of pairs of numbers in the array s.t a[i] < a[j].
Solution:
First you find the set of all distinct elements in the array {x(1), …, x(M)} with x(i) < x(i+1) and their corresponding counts {c(1),…,c(M). Now it is easy to see that the required number of such pairs is
Sum_{i} (c(i) * (c(1)+…c(i-1))
This is simply
Sum_{i} (c(i) * c_cumulative(i-1))
where c_cumulative(k) is the cumulative sum of c() that can be computed in O(M) time. Thus, the total counts of such pairs can be computed in O(N).
The problem describes that all integers are distinct. Therefore any two integers, say (ai, aj), will satisfy the property ai < aj or aj < ai. Two integers can be picked up in NC2 ways. So the answer is simply N*(N-1)/2.
import java.util.;
class Sol
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-- > 0)
{
int n=sc.nextInt();
long x=0;
for(int i=0;i<n;i++)
x=sc.nextLong();
System.out.println((n(n-1)/2));
This is a very straightforward and easy problem. As it is provided that all the values in the array are distinct then all the possible pairings in the sorted array are valid which by applying a little mathematics is n*(n - 1)/2.
