# Modified Counting Inversions problem using divide and conquer

Given an array $A$, find the number of pairs $(i, j)$, such that $i > j$ and $A[i] \ge A[j]$.

This is a modified version of the famous problem of Counting Inversions, only in this version it allows the elements to be equal as well. I have an algorithm for the classical counting inversions problem implemented, so i´d like to know if it can be adapted to solve this version. Thanks ahead.

Link to the algorithm (written in C++):

https://repl.it/@MateusBuarque/CountingInversion

• Your link 404s so I've no idea what your algorithm is. Also, people shouldn't have to understand C++ to understand an algorithm: could you please supply the algorithm, in pseudocode, in your question? – David Richerby Apr 24 '18 at 12:25
• I'm voting to close this question as off-topic because this is no site for "comment my code" type questions. – vonbrand Apr 27 '18 at 14:11

Can you count the number of pairs $(i,j)$ such that $A[i]=A[j]$?
• yes, but only in $O(n^2)$. Oh wait, i get it now... – Mateus Buarque Apr 23 '18 at 17:04
• @MateusBuarque, well then you have something you can think about! Spend some more time on that problem. It's your exercise, so you'll have to find the solution yourself -- but you can do better than $O(n^2)$. – D.W. Apr 23 '18 at 17:05