Made Easy Test Series:Algorithm-Inversion

Question

Consider an array $A=\left \{ 30,15,48,34,26,29 \right \}$

Let $X$ be the number of inversion of array $A,$ Now another array $B$ is constructed by making all the numbers in $A$ negative and keeping the order between each numbers same. Let the number of inversion of the modified array so obtained be $Y.$ Then $X+2Y=$_______________

---

$\left ( 30,26 \right )$ number of inversion $4$ or $1??$

Answer 1

The inversions in array $A$ are $(30, 15), (30, 26), (30, 29), (48, 34), (48, 26), (48, 29), (34, 26), (34, 29)$.

Number of inversions = $8$

The inversions in array $B$ are $(-30, -48), (-30, -34), (-15, -48), (-15, -34), (-15, -26), (-15, -29), (-26, -29)$.

Number of inversions = $7$

Therefore, $X = 8$ and $Y = 7$

$X + 2Y = 8 + 2*7 = 8 + 14 = 22$

Answer 2

Only 1 inversion as 

in inversion, i < j but a[i] > a[j].

Comments

thanks :)