Question 23 An inversion in a an array A[] is a pair (A[i], A[j]) such that A[i] A[j] and i...
Palo Alto Networks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
An inversion in a an array A[] is a pair (A[i], A[j]) such that A[i] > A[j] and i < j. An array will have maximum number of inversions if it is
Select any one of the following options
Show answer & explanation
An array of size n sorted in strictly decreasing order has every pair (i, j) with i < j satisfying A[i] > A[j], maximizing inversions at n(n-1)/2.
Step-by-step Derivation:
Step 1: An inversion is defined as a pair (A[i], A[j]) such that i < j and A[i] > A[j].
Step 2: The total number of pairs in an array of length n is n(n-1)/2.
Step 3: When the array is sorted in descending order, every single pair satisfies A[i] > A[j], achieving the maximum possible inversions n(n-1)/2.