本周的tiktok OA不当人啦，连续出了3个hard级别的算法题，我们一起来看看其中一道题吧。

The TikTok online assessment this week is outrageously difficult; they've presented us with three hard-level algorithm questions in a row. Let's take a look at one of them together.

Q3.Minimum Inversions

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

Example n = 3 arr = [8,5,2]

Value of x to test	New Array	Number of Inversions
4	[8⨁4, 5⨁4, 2⨁4]= [12, 1, 6]	2
3	[8⨁3, 5⨁3, 2⨁3]= [11, 6, 7]	2
12	[8⨁12, 5⨁12, 2⨁12]= [4, 9, 14]	0

In the first row, after the elements are XORed with 4, there are two inversions. For (i=1, j=2, arr[1] = 1 and arr[j] = 6 For (i=1, j=2, arr[1] = 6 and arr[j] = 12.

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

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

Constraints

• 1 ≤ n ≤ 10^5
• 0 ≤ arr[i] ≤ 10^9

Input Format For Custom Testing
The first line contains an integer, n, the size of arr[].
Each of the next n lines contains an integer arr[i].

Sample Input 0

STDIN Function

---

4 > arr[] size n = 4
0 > arr = [0, 8, 2, 4]
8
2
4

Sample Output 0
1

Explanation

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

Sample Case 1

Sample Input 1

5 > arr[] size n = 5
17 > arr = [17, 12, 5, 10, 22]

Sample Output 1
5

Explanation

Here:
n = 5
arr = [(17,12,5,10,22]

后续我会在网站上陆续公布剩余的题目 ，或者联系我，查看我们的服务。

If you're afraid that you can't solve the OA on your own, please scan the code to contact me or telegram