#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