Count Inversions in Array in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the inversion count variable.

DSA C#

int count = [1];

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

A1

B-1

C0

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Starting count from 1 instead of 0

Using null or negative values for count

We start counting inversions from zero because initially no pairs are counted.

2fill in blank

medium

Complete the code to compare elements for inversion detection.

DSA C#

if (arr[i] [1] arr[j])

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

A>

B<

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using less than operator which detects non-inversions

Using equality operator which does not detect inversions

An inversion is when a larger element appears before a smaller one, so we check if arr[i] > arr[j].

3fill in blank

hard

Fix the error in the nested loop condition to avoid out-of-range errors.

DSA C#

for (int j = i + 1; j [1] arr.Length; j++)

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

A<=

B<

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= causes index out of range error

Using > or >= reverses the loop logic

The loop should run while j is less than arr.Length to stay within array bounds.

4fill in blank

hard

Fill both blanks to correctly increment the inversion count inside the nested loops.

DSA C#

if (arr[i] [1] arr[j]) {
    count [2];
}

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

A>

B++

C+=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect comparison operators

Using += without a value or wrong increment

We check if arr[i] > arr[j] to find an inversion, then increment count by 1 using ++.

5fill in blank

hard

Fill all three blanks to complete the method that counts inversions in an array.

DSA C#

public static int CountInversions(int[] arr) {
    int count = [1];
    for (int i = 0; i [2] arr.Length - 1; i++) {
        for (int j = i + 1; j [3] arr.Length; j++) {
            if (arr[i] > arr[j]) {
                count++;
            }
        }
    }
    return count;
}

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

A0

B<

C<=

Attempts:

3 left

💡 Hint

Common Mistakes

Incorrect loop bounds causing index errors

Wrong initialization of count variable

Initialize count to 0. Outer loop runs while i < arr.Length - 1. Inner loop runs while j < arr.Length.

Practice

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

easy

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

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

C. The total number of elements in the array

D. The sum of all elements in the array

Solution

1. Step 1: Understand the definition of inversion

   An inversion is a pair of elements (i, j) such that i < j but array[i] > array[j].

2. Step 2: Compare options with definition

   A pair of elements where the first is greater than the second and appears before it correctly describes this condition, while others describe unrelated concepts.

3. Final Answer:

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

4. Quick Check:

   Inversion = pair (i, j) with i < j and array[i] > array[j] [OK]

Hint: Inversion means earlier bigger number than a later one [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts pairs where first is smaller
• Counting total elements instead of pairs

2. Which of the following C# code snippets correctly initializes an integer array named arr with values 3, 1, 2?

easy

A. int arr[] = new int[3] {3, 1, 2};

B. int arr = {3, 1, 2};

C. int[] arr = new int[] {3, 1, 2};

D. int arr[] = {3, 1, 2};

Solution

1. Step 1: Review C# array initialization syntax

   In C#, arrays must be declared as int[] arr and can be initialized explicitly with new int[] {values};

2. Step 2: Check each option

   int arr[] = new int[3] {3, 1, 2}; uses invalid declaration syntax (arr[]). int arr = {3, 1, 2}; tries to assign an array to an int. int arr[] = {3, 1, 2}; uses invalid declaration syntax (arr[]). int[] arr = new int[] {3, 1, 2}; uses the correct explicit syntax.

3. Final Answer:

   int[] arr = new int[] {3, 1, 2}; -> Option C

4. Quick Check:

   Correct array init uses new int[] {values} [OK]

Hint: Use new int[] { } to initialize arrays explicitly [OK]

Common Mistakes:

• Omitting new int[] in initialization
• Using C/C++ style array declaration
• Incorrect array size syntax

3. What is the output of the following C# code that counts inversions in the array arr = {2, 4, 1, 3, 5}?

int CountInversions(int[] arr) {
    int count = 0;
    for (int i = 0; i < arr.Length - 1; i++) {
        for (int j = i + 1; j < arr.Length; j++) {
            if (arr[i] > arr[j]) count++;
        }
    }
    return count;
}

int[] arr = {2, 4, 1, 3, 5};
Console.WriteLine(CountInversions(arr));

medium

A. 3

B. 4

C. 2

D. 5

Solution

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

   Pairs where first > second and first index < second index: (2,1), (4,1), (4,3) -> total 3 inversions.

2. Step 2: Confirm code counts these pairs

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

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count inversions in {2,4,1,3,5} = 3 [OK]

Hint: Count pairs where earlier number is bigger than later [OK]

Common Mistakes:

• Counting pairs where first is smaller
• Missing some inversion pairs
• Off-by-one errors in loops

4. The following code attempts to count inversions but gives wrong output. What is the error?

int CountInversions(int[] arr) {
    int count = 0;
    for (int i = 0; i < arr.Length; i++) {
        for (int j = 0; j < arr.Length; j++) {
            if (arr[i] > arr[j]) count++;
        }
    }
    return count;
}

medium

A. The function should return void

B. Comparison should be arr[i] < arr[j]

C. Count variable should be initialized outside the function

D. Inner loop should start from i+1, not 0

Solution

1. Step 1: Analyze loop ranges for counting inversions

   Inversion pairs require i < j, but inner loop starts at 0, counting pairs twice and including invalid pairs.

2. Step 2: Fix inner loop start index

   Changing inner loop to start at i+1 ensures only pairs with i < j are counted once.

3. Final Answer:

   Inner loop should start from i+1, not 0 -> Option D

4. Quick Check:

   Count inversions need j > i, so inner loop from i+1 [OK]

Hint: Inner loop must start after outer index to avoid double count [OK]

Common Mistakes:

• Starting inner loop at 0 causing double counting
• Reversing comparison operator
• Misplacing count initialization

5. Given the array arr = {8, 4, 2, 1}, what is the total number of inversions? Use the efficient merge sort based method to count inversions.

hard

A. 7

B. 6

C. 4

D. 5

Solution

1. Step 1: Understand inversions in the array

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

2. Step 2: Count inversions using merge sort method

   Subarrays [8,4] and [2,1] each add 1 inversion (total 2). Final merge of [4,8] and [1,2]: +2 when taking 1, +2 when taking 2 (total 4). Grand total: 6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Merge sort inversion count for {8,4,2,1} = 6 [OK]

Hint: Merge sort counts inversions during merge step [OK]

Common Mistakes:

• Counting only direct pairs, missing cross merges
• Using brute force count only
• Misunderstanding merge step inversion counting