# 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.

### 12 Replies to “Solution to Array-Inversion-Count by codility”

1. Andrew says:

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

• Sheng says:

Wonderful morning! Learn something new! THAAAAAANKS!!!

2. Pufface says:

My solution using binary search and sorted array.

[code was removed by admin, because of missing tag/content]

• Doc says:

This is horrible. Did you at least check if it compiles?

• Sheng says:

Part of the code should be missing, without the pre tags. I’ve removed the incomplete code.

3. Doc says:

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?

• Sheng says:

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 ðŸ™‚

• Doc says:

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.

4. Jekt31 says:

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.

5. Luiz doleron says:

This is my C++ solution:
https://app.codility.com/demo/results/trainingYJX2GY-6RU/