hardDynamic Programming 1DAI-applied~35 min
Assign Predictions to Targets Minimizing Total XOR
You must pair each predicted code with exactly one ground-truth code. The cost of a pairing is the XOR of the two codes (a bitwise mismatch penalty). Find the one-to-one assignment with minimum total XOR.
Problem
Given two integer arrays nums1 and nums2 of equal length n, find a bijection (rearrangement of nums2) minimizing the XOR sum: the sum over i of (nums1[i] XOR nums2[perm[i]]). Return that minimum XOR sum.
Input
Two equal-length integer arrays nums1 and nums2.
Output
An integer: the minimum achievable XOR sum.
Constraints
- 1 <= n <= 14
- 0 <= nums1[i], nums2[i] <= 10^7
Examples
Example 1
Input
nums1 = [1,2], nums2 = [2,3]
Output
2
Pair 1 with 3 (XOR 2) and 2 with 2 (XOR 0): total 2.
Example 2
Input
nums1 = [1,0,3], nums2 = [5,3,4]
Output
8
The best assignment yields total XOR 8.