FastPrep
Problem · Array

Minimum Inversions 🍑

Learn this problem
● HardTiktokNEW GRADOA
See Tiktok hiring insights

Problem 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[]) → long

Examples

Example 1

arr = [8, 5, 2]return = 0
Value of x to testNew ArrayNumber 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 testNew ArrayNumber of Inversions
4[4, 12, 6, 0]4
8[8, 0, 10, 12]1
12[12, 4, 14, 8]3

Constraints

  • 1 <= n <= 105
  • 0 <= arr[i] <= 109

    • More Tiktok problems

    drafts saved locally
    public long findMinInversions(int[] arr) {
    // write your code here
}
    arr[8, 5, 2]
    expected0
    checking account