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.

11 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:
    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. Hi Sheng,

    I tried running your Solution (not the Wrong Solution) and it is exceeding recursion limit. Could you please check if this is not the case?

    • When I finished the problem, the site was using Python 2.X. While nowadays, they switched to Python3. As a result, the divide op “/” is changed, at line #5. I have updated the solution for Python 3. Thanks for pointing it out 🙂

      • My bad, I didn’t think about the version issue. Anyway, thanks a lot for updating the solution. I was looking at the BIT solution and honestly, I don’t get it.

  3. Here is my 100/100 solution in C#.
    Algorithm is quite easy : create a sorted copy of the list, then for each value of the first list, binary search its index in the sorted one. That index corresponds to the number of inversions.
    Then remove the value you just searched from the sorted list, and repeat.

Leave a Reply

Your email address will not be published.

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