FastPrepFastPrep
Problem Brief

Minimum Inversions 🍑

NEW GRADOA
See Tiktok online assessment and hiring insights

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:

  1. int arr[n]: the array

Returns

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

1Example 1

Input
arr = [8, 5, 2]
Output
0
Explanation
Example 1 illustration
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.

2Example 2

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

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= n <= 105
  • 0 <= arr[i] <= 109
    • public int findMinInversions(int[] arr) {
    // write your code here
}
    Input

    arr

    [8, 5, 2]

    Output

    0

    Sign in to submit your solution.