Solution to Array-Inversion-Count by codility

4 Feb

Question: https://codility.com/demo/take-sample-test/array_inversion_count

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 thoughts on “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:
    https://codility.com/demo/results/demoSD6QAC-XDX/

    And a great write up of how to use a BIT to solve the inversion counting problem is here:
    http://pavelsimo.blogspot.co.uk/2012/09/counting-inversions-in-array-using-BIT.html

  2. My solution using binary search and sorted array.

Leave a Reply

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