Underdog_eagle's blog

By Underdog_eagle, history, 2 years ago, In English,

Problem Statement :-

Alexandra has some distinct integer numbers a1,a2...an. Count number of pairs (i,j) such that:

  • 1≤ i ≤ n
  • 1≤ j ≤ n
  • a[i] < a[j]

Constraints :-

  • 1 ≤ n ≤ 100000
  • 0 ≤ a[i] ≤ 10^9
  • All the a[i] are distinct

Solution :-

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.

Explanation :-

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Underdog_eagle (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

its very Obvious solution and doesn't need blog.

C (n , 2) --> checking all pairs