ALEXNUMB - Editorial

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.

8 Likes

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));

}

}
}

//What is wrong in this??

@chauhan_1111 Be careful that Integer.MAX_VALUE < 100000 * 99999. Just change this:

int n=sc.nextInt() --> long n=sc.nextLong()

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.

Mind the size of the resulting number :wink:

//