HardNo. 1787
Make the XOR of All Segments Equal to Zero — LeetCode 1787 Python Solution
- Pattern
- Bit Manipulation
- Topics
- Bit Manipulation, Array, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given an array nums and an integer k. The XOR of a segment [left, right] where left <= right is the XOR of all the elements with indices between left and right, inclusive: nums[left] XOR nums[left+1] XOR ...
Example
- Input
- nums = [1,2,0,3,0], k = 1
- Output
- 3
- Explanation
- Modify the array from [1,2,0,3,0] to from [0,0,0,0,0].
Python solution
class Solution:
def minChanges(self, nums: List[int], k: int) -> int:
n = 1 << 10
cnt = [Counter() for _ in range(k)]
size = [0] * k
for i, v in enumerate(nums):
cnt[i % k][v] += 1
size[i % k] += 1
f = [inf] * n
f[0] = 0
for i in range(k):
g = [min(f) + size[i]] * n
for j in range(n):
for v, c in cnt[i].items():
g[j] = min(g[j], f[j ^ v] + size[i] - c)
f = g
return f[0]Complexity
- Time
- O(2C × k + n)
- 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 1787. Make the XOR of All Segments Equal to Zero is filed here because LeetCode tags it Bit Manipulation, 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 |
| 0898 | Bitwise ORs of Subarrays | Medium |
Frequently asked questions
- How hard is LeetCode 1787. Make the XOR of All Segments Equal to Zero?
LeetCode 1787. Make the XOR of All Segments Equal to Zero is rated Hard on LeetCode.
- What topics does LeetCode 1787. Make the XOR of All Segments Equal to Zero cover?
LeetCode 1787. Make the XOR of All Segments Equal to Zero is tagged Bit Manipulation, Array and Dynamic Programming on LeetCode.