#TestBook

Question

Suppose in an array A[] , we exchange elements A[i] and A[i+k] , which were originally out of order
A) at least 1 and at most 2k-1 inversions are removed
B) at least 2 and at most 2k inversions are removed
C)at least 0 and at most k  inversions are removed
D) none

Comments

Ans is A
is it?

---

@srestha YES but how  ?

---

Please can you explain the logic?

---

Suppose i=0 and k=1

So, we want to inversion of a[0] and a[1], which can be done in with 1 inversion

Now index k>=i

So, maximum i=k

index of a[i+k]=a[k+k]=a[2k]

So, maximum inversion from 0 th index is 2k-1

Answer 1

Elements	5	4	3	2	1
Inversions	4	3	2	1	0

Total Inversions = 4+3+2+1+0 =10

1. for minimum, let k=1 , swap(a[0],a[0+1])

Elements	4	5	3	2	1
Inversions	3	3	2	1	0

Total Inversions = 3+3+2+1+0 =9

difference =1

2. now, let k= 2, swap(a[0],a[0+2])

Elements	3	4	5	2	1
Inversions	2	2	2	1	0

Total Inversions = 2+2+2+1+0 =7

difference =3

From 1 and 2:

Option A satisfies.