Count Inversions in Array in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Count inversions in a small array

What is the output of the following C code that counts inversions in the array?

DSA C

#include <stdio.h>

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

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

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

A 3

B 4

C 2

D 5

💡 Hint

Count pairs (i, j) where i < j and arr[i] > arr[j].

The array has three inversions: (2,1), (4,1), and (4,3). The code uses merge sort to count these efficiently.

🧠 Conceptual

intermediate

Understanding inversion count concept

Which of the following best describes what an inversion in an array means?

A A pair of elements where the first is smaller and appears before the second.

B A pair of elements where the first is larger and appears before the second.

C A pair of elements that are equal and adjacent.

D A pair of elements where the second is larger and appears before the first.

💡 Hint

Think about pairs that are out of order.

An inversion is when a bigger number appears before a smaller number in the array.

❓ Predict Output

advanced

Count inversions in a reversed array

What is the output of the following C code counting inversions in a reversed array?

DSA C

#include <stdio.h>

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

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

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

A 15

B 5

C 10

D 0

💡 Hint

Count all pairs where a bigger number appears before a smaller one in a reversed array.

A reversed array of size 5 has maximum inversions: 5*4/2 = 10.

🔧 Debug

advanced

Identify the bug in inversion count code

What error will the following code produce when counting inversions?

DSA C

#include <stdio.h>

int merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid, k = left, inv_count = 0;
    while ((i <= mid) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            inv_count += (mid - i + 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;
}

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

int main() {
    int arr[] = {2, 3, 8, 6, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int temp[n];
    int result = mergeSort(arr, temp, 0, n - 1);
    printf("%d\n", result);
    return 0;
}

A The code outputs 4 instead of 5

B The code causes an infinite loop

C The code runs correctly and outputs 5

D The code causes a segmentation fault

💡 Hint

Check the merge function's loop conditions and indices carefully.

The merge function uses wrong mid index boundaries causing it to miss counting one inversion, resulting in output 4 instead of 5.

🚀 Application

expert

Find number of inversions after multiple updates

Given an array and multiple update operations that change elements, which data structure is best suited to efficiently count inversions after each update?

A Queue to process elements in order

B Simple array traversal after each update

C Stack to store elements and count inversions

D Segment Tree with Merge Sort Tree or BIT with offline queries

💡 Hint

Think about data structures that support fast range queries and updates.

Segment Trees or Binary Indexed Trees combined with merge sort logic allow efficient inversion counting after updates, unlike simple traversal which is too slow.