HardNo. 1879
Minimum XOR Sum of Two Arrays — LeetCode 1879 Python Solution
- Pattern
- Bit Manipulation
- Topics
- Bit Manipulation, Array, Dynamic Programming, Bitmask
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given two integer arrays nums1 and nums2 of length n. The XOR sum of the two integer arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ...
Example
- Input
- nums1 = [1,2], nums2 = [2,3]
- Output
- 2
- Explanation
- Rearrange nums2 so that it becomes [3,2].
Python solution
class Solution:
def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums2)
f = [[inf] * (1 << n) for _ in range(n + 1)]
f[0][0] = 0
for i, x in enumerate(nums1, 1):
for j in range(1 << n):
for k in range(n):
if j >> k & 1:
f[i][j] = min(f[i][j], f[i - 1][j ^ (1 << k)] + (x ^ nums2[k]))
return f[-1][-1]Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1879. Minimum XOR Sum of Two Arrays is filed here because LeetCode tags it Bit Manipulation and Bitmask, which is the vocabulary this hub collects.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0473 | Matchsticks to Square | Medium |
| 0526 | Beautiful Arrangement | Medium |
| 0638 | Shopping Offers | Medium |
| 0698 | Partition to K Equal Sum Subsets | Medium |
| 0805 | Split Array With Same Average | Hard |
| 0943 | Find the Shortest Superstring | Hard |
Frequently asked questions
- How hard is LeetCode 1879. Minimum XOR Sum of Two Arrays?
LeetCode 1879. Minimum XOR Sum of Two Arrays is rated Hard on LeetCode.
- What topics does LeetCode 1879. Minimum XOR Sum of Two Arrays cover?
LeetCode 1879. Minimum XOR Sum of Two Arrays is tagged Bit Manipulation, Array, Dynamic Programming and Bitmask on LeetCode.