FastPrep

Description

Solutions

Minimum Inversions 🍑

👩‍🎓 NEW GRAD📚RELATED PROBLEMS

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].

Function Description

Complete the function findMinInversions in the editor below.

findMinInversions has the following parameter:

int arr[n]: the array

Returns

int: the minimum possible number of inversions after modifying the array with integer x

Example 1:

Input:  arr = [8, 5, 2]
Output: 0 
Explanation:
See above image 👆😳

In the first row, after the elements are XORed with 4, there are two inversions.

For [i, j] = [1, 0], and arr[0] = 1 and arr[1] = 12.
For [i, j] = [2, 0], arr[0] = 6 and arr[1] = 12.

For x = 12 the number of inversions is 0. This is the minimum possible, so the answer is 0.

Example 2:

Input:  arr = [0, 8, 2, 4]
Output: 1 
Explanation:

Constraints:

1 <= n <= 10⁵

0 <= arr[i] <= 10⁹