Count Inversions in Array in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the number of inversions in the array segment.

DSA C

int merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    int inv_count = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            inv_count += [1];
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (i = left; i <= right; i++) arr[i] = temp[i];
    return inv_count;
}

Drag options to blanks, or click blank then click option'

Amid - i + 1

Bj - i + 1

Cright - j + 1

Dmid + j - i

Attempts:

3 left

💡 Hint

Common Mistakes

Counting only one inversion instead of all from i to mid.

Using wrong indices for counting.

When arr[i] > arr[j], all elements from i to mid are greater than arr[j], so count is mid - i + 1.

2fill in blank

medium

Complete the recursive function to count inversions in the array.

DSA C

int mergeSort(int arr[], int temp[], int left, int right) {
    int mid, inv_count = 0;
    if (left < right) {
        mid = [1];
        inv_count += mergeSort(arr, temp, left, mid);
        inv_count += mergeSort(arr, temp, mid + 1, right);
        inv_count += merge(arr, temp, left, mid, right);
    }
    return inv_count;
}

Drag options to blanks, or click blank then click option'

Aleft - right

B(left + right) / 2

Cleft + right

Dright - left

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition without division causing overflow.

Using subtraction which gives wrong midpoint.

Midpoint is the average of left and right indices, integer division.

3fill in blank

hard

Fix the error in the merge function to correctly copy elements back to the original array.

DSA C

for (i = [1]; i <= right; i++) arr[i] = temp[i];

Drag options to blanks, or click blank then click option'

Aleft

B0

Cmid

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Starting copy from 0 causes overwriting unrelated parts.

Starting from mid misses some elements.

Copying back must start from left index to right index.

4fill in blank

hard

Fill both blanks to complete the main function that counts inversions.

DSA C

int main() {
    int arr[] = {2, 4, 1, 3, 5};
    int n = sizeof(arr) / sizeof(arr[[1]]);
    int temp[n];
    int result = mergeSort(arr, temp, 0, [2]);
    printf("Number of inversions: %d\n", result);
    return 0;
}

Drag options to blanks, or click blank then click option'

A0

B1

Carr

Dn - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using arr or 1 instead of 0 for size calculation.

Passing n instead of n-1 as last index.

Size calculation uses arr[0], and last index is n-1 for mergeSort.

5fill in blank

hard

Fill all three blanks to complete the merge function's while loop condition and increment.

DSA C

while (i <= [1] && j <= [2]) {
    if (arr[i] <= arr[j]) {
        temp[k++] = arr[i++];
    } else {
        temp[k++] = arr[j++];
        inv_count += [3];
    }
}

Drag options to blanks, or click blank then click option'

Amid

Bright

Cmid - i + 1

Dright - j + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong boundary for i or j.

Counting inversions incorrectly.

i runs to mid, j runs to right, inversions counted as mid - i + 1.