Description
Solutions
Submission
Minimum Inversions šŸ‘
šŸ”„ FULLTIME

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

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 <= 105
  • 0 <= arr[i] <= 109
Thumbnail 0
Thumbnail 1
Testcase
Result
Case 1

input:

output: