HardDpAI interview only
Minimum XOR Sum of Two Arrays
Asked atgoogleamazonmicrosoft
01 · Problem
You are given two integer arrays nums1 and nums2 of the same length n. The XOR sum of the two arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n-1] XOR nums2[n-1]).
You may reorder the elements of nums2 in any way you like (nums1 stays fixed). Return the smallest possible XOR sum.
02 · Examples
Example 01
Input
nums1 = [1,2], nums2 = [2,3]
Output
2
Reorder nums2 to [3,2]. The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.
Example 02
Input
nums1 = [1,0,3], nums2 = [5,3,4]
Output
8
Reorder nums2 to [5,4,3]. The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.
03 · Constraints
- 01n == nums1.length == nums2.length
- 021 <= n <= 14
- 030 <= nums1[i], nums2[i] <= 107
04 · Optimal complexity
- Time
- O(n * 2^n)
- Space
- O(2^n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.