Minimum Inversions 🍑
Learn this problem
TiktokNEW GRADOAProblem statement
Given an array of n integers, arr[n], find the value of x that can be applied to the array to minimize the number of inversions. The array can be modified by applying the bitwise XOR to each element of the array with x. The symbol ⊕ means XOR in the example.
An inversion in an array arr is a pair of indices (i, j) where i > j and arr[i] < arr[j].
Complete the function findMinInversions in the editor below.
findMinInversions has the following parameter:
int arr[n]: the array
long: the minimum possible number of inversions after modifying the array with integer x.
Function
findMinInversions(arr: int[]) → longExamples
Example 1
arr = [8, 5, 2]return = 0| Value of x to test | New Array | Number of Inversions |
|---|---|---|
| 4 | [8⊕4, 5⊕4, 2⊕4] = [12, 1, 6] | 2 |
| 3 | [11, 6, 7] | 2 |
| 12 | [4, 9, 14] | 0 |
In the first row, after the elements are XORed with 4, there are two inversions.
For [i, j] = [1, 0], arr[i] = 1 and arr[j] = 12. For [i, j] = [2, 0], arr[i] = 6 and arr[j] = 12.
For x = 12, the number of inversions is 0. This is the minimum possible, so the answer is 0.
Example 2
arr = [0, 8, 2, 4]return = 1| Value of x to test | New Array | Number of Inversions |
|---|---|---|
| 4 | [4, 12, 6, 0] | 4 |
| 8 | [8, 0, 10, 12] | 1 |
| 12 | [12, 4, 14, 8] | 3 |