#3811
Number of Alternating XOR Partitions
medium · 26.6% accepted · 86 likes · top 5%
array · hash table · dynamic programming · bit manipulation
Description
You are given an integer array nums and two distinct integers target1 and target2.
A partition of nums splits it into one or more contiguous, non-empty blocks that cover the entire array without overlap.
A partition is valid if the bitwise XOR of elements in its blocks alternates between target1 and target2, starting with target1.
Formally, for blocks b1, b2, …:
- XOR(b1) = target1
- XOR(b2) = target2 (if it exists)
- XOR(b3) = target1, and so on.
Return the number of valid partitions of nums, modulo 109 + 7.
Note: A single block is valid if its XOR equals target1.
Solution