0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – David Richerby Apr 24 '18 at 12:25
  • $\begingroup$ I'm voting to close this question as off-topic because this is no site for "comment my code" type questions. $\endgroup$ – vonbrand Apr 27 '18 at 14:11
1
$\begingroup$

Hint:

Can you count the number of pairs $(i,j)$ such that $A[i]=A[j]$?

$\endgroup$
  • $\begingroup$ yes, but only in $O(n^2)$. Oh wait, i get it now... $\endgroup$ – Mateus Buarque Apr 23 '18 at 17:04
  • $\begingroup$ @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)$. $\endgroup$ – D.W. Apr 23 '18 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.