Question

What is the condition for two elements arr[i] and arr[j] to form an inversion?

(a) arr[i]<arr[j]

(b) i < j

(c) arr[i] < arr[j] and i < j

(d) arr[i] > arr[j] and i < j

The question is from Arrays Types topic in section Arrays Types of Data Structures & Algorithms I

The question was asked in an international level competition.

Answer 1

Correct choice is (d) arr[i] > arr[j] and i < j

The explanation is: For two elements to form an inversion the necessary condition is arr[i] > arr[j] and i < j. The number of inversions in an array indicate how close or far the array is from being completely sorted.