GATE 2025 DA Q.29: solution and answer

Official answer: A, CSource: Official answer key, GATE 2025 DA (IIT Roorkee)

1. Insertion sort moves each element left by adjacent swaps until it reaches its place. Each adjacent swap removes exactly one inversion, and the sort ends with none. So the number of swaps equals the number of inversions, meaning pairs $i<j$ with $a_i>a_j$. We need exactly $2$ inversions.

2. The pair $(15,13)$ is already an inversion, so it contributes $1$. The entries $1,3,5,7,9,11$ are increasing and smaller than $15$ and $13$, so no other pair among the fixed entries is an inversion. We therefore need exactly $1$ inversion that involves $x$.

3. Inversions involving $x$ = (number of earlier elements in $\{1,3,5,7,9,11\}$ greater than $x$) + (number of later elements in $\{15,13\}$ smaller than $x$).

4. $x=10$: only $11>10$ is greater among the earlier elements, giving $1$. Neither $15$ nor $13$ is smaller than $10$, giving $0$. Total with $x$ is $1$, so the array has $2$ inversions and takes $2$ swaps. Valid.

5. $x=12$: no earlier element exceeds $12$, and neither $15$ nor $13$ is smaller than $12$. That gives $0$ inversions with $x$, so the array has $1$ inversion and takes $1$ swap. Not valid.

6. $x=14$: no earlier element exceeds $14$. Among the later elements, $13<14$ counts and $15<14$ does not, giving $1$. The array has $2$ inversions and takes $2$ swaps. Valid.

7. $x=16$: no earlier element exceeds $16$, but both $15<16$ and $13<16$ count, giving $2$. The array has $3$ inversions and takes $3$ swaps. Not valid.

8. Hence the possible values are $x=10$ and $x=14$, which are options (A) and (C).