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.

Practice

1. What does the term inversion in an array mean?

easy

A. The total number of elements in the array

B. A pair of elements where the first is greater than the second and appears before it

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

D. The sum of all elements in the array

Solution

1. Step 1: Understand the definition of inversion

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

2. Step 2: Compare options with definition

   A pair of elements where the first is greater than the second and appears before it matches this definition exactly, others describe different concepts.

3. Final Answer:

   A pair of elements where the first is greater than the second and appears before it -> Option B

4. Quick Check:

   Inversion = larger before smaller [OK]

Hint: Inversion means bigger number comes before smaller one [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts equal elements
• Mixing inversion with total pairs

2. Which of the following C code snippets correctly declares a function to count inversions in an array?

easy

A. int countInversions(int arr[], int n);

B. void countInversions(int arr[], int n);

C. int countInversions(int arr, int n[]);

D. int countInversions(int *arr, int n[]);

Solution

1. Step 1: Check function signature correctness

   The function should return an integer count and take an integer array and its size as parameters.

2. Step 2: Analyze each option

   int countInversions(int arr[], int n); correctly uses int return type and parameters as int arr[] and int n. Others have wrong parameter types or return type.

3. Final Answer:

   int countInversions(int arr[], int n); -> Option A

4. Quick Check:

   Correct function signature returns int and takes int array and size [OK]

Hint: Function returns int and takes int array plus size [OK]

Common Mistakes:

• Using void return type instead of int
• Swapping array and size parameter types
• Using pointer syntax incorrectly

3. What is the output of the following C code snippet?

int arr[] = {2, 4, 1, 3, 5};
int n = 5;
int count = 0;
for(int i = 0; i < n-1; i++) {
  for(int j = i+1; j < n; j++) {
    if(arr[i] > arr[j]) count++;
  }
}
printf("%d", count);

medium

A. 5

B. 4

C. 3

D. 2

Solution

1. Step 1: Identify all inversion pairs in the array

   Pairs where first element is greater than second: (2,1), (4,1), (4,3). Total = 3.

2. Step 2: Confirm count variable increments correctly

   Nested loops check all pairs; count increments for each inversion found, total 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Inversions = 3 [OK]

Hint: Count pairs where left element > right element [OK]

Common Mistakes:

• Counting pairs where left < right
• Missing some inversion pairs
• Off-by-one errors in loops

4. The following code is intended to count inversions but has a bug. What is the bug?

int countInversions(int arr[], int n) {
  int count = 0;
  for(int i = 0; i < n; i++) {
    for(int j = i; j < n; j++) {
      if(arr[i] >= arr[j]) count++;
    }
  }
  return count;
}

medium

A. Inner loop should start from j = i + 1, not j = i

B. The count variable should be initialized outside the function

C. The comparison should be arr[i] < arr[j]

D. The function should return void instead of int

Solution

1. Step 1: Analyze loop ranges for counting pairs

   Inner loop starts at j = i, so it compares arr[i] with itself, causing incorrect counting.

2. Step 2: Correct inner loop start index

   Inner loop should start at j = i + 1 to avoid self-comparison.

3. Final Answer:

   Inner loop should start from j = i + 1, not j = i -> Option A

4. Quick Check:

   Start inner loop at i+1 to avoid self-comparison [OK]

Hint: Inner loop must start after outer loop index [OK]

Common Mistakes:

• Starting inner loop at same index as outer
• Wrong comparison operator
• Returning wrong type

5. Given the array {8, 4, 2, 1}, what is the total number of inversions? Also, explain why this number represents the worst case for inversion counting.

hard

A. 4

B. 0

C. 3

D. 6

Solution

1. Step 1: Count all inversion pairs in the array

   Pairs: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) total 6 inversions.

2. Step 2: Understand why this is worst case

   The array is sorted in descending order, so every pair is inverted, maximum inversions possible for size 4.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Descending order array has max inversions = n(n-1)/2 [OK]

Hint: Descending order array has max inversions n(n-1)/2 [OK]

Common Mistakes:

• Counting only adjacent inversions
• Forgetting pairs with elements far apart
• Confusing inversion count with array length