Solution to Array-Inversion-Count by codility

4 Feb


Question Name: ArrayInversionCount

UPDATE on July 18, 2014: Thanks to @Andrew, there is another solution with Binary Indexed Tree.

UPDATE on October 8, 2014: Thanks to @Piotrek Martynowicz, there was a bug for the statement: “computes the number of inversions in A, or returns −1 if it exceeds 1,000,000,000.

5 Replies to “Solution to Array-Inversion-Count by codility

  1. This problem can also be solved in O(n * log n) time and O(n) space by using a Binary Indexed Tree (aka Fenwick Tree).

    The basic idea is to use the BIT to keep track, during a right to left scan of the input, of the cumulative frequency of elements previously seen that are strictly less than the current element.

    My implementation of this idea is here:

    And a great write up of how to use a BIT to solve the inversion counting problem is here:

  2. My solution using binary search and sorted array.

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!