Challenge: Number of Inversions

Solve the Number of Inversions Problem.

We'll cover the following

Problem


Number of Inversions Problem

Compute the number of inversions in a sequence of integers.

Input: A sequence of nn integers a1,,ana_{1},\ldots,a_{n}.
Output: The number of inversions in the sequence—that is, the number of indices i<ji < j such that ai>aja_{i} > a_{j}.


Level up your interview prep. Join Educative to access 80+ hands-on prep courses.