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) = target1XOR(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.
Example 1:
Input: nums = [2,3,1,4], target1 = 1, target2 = 5
Output: 1
Explanation:
[2, 3] is 1, which matches target1.[1, 4] is 5, which matches target2.Example 2:
Input: nums = [1,0,0], target1 = 1, target2 = 0
Output: 3
Explanation:
[1, 0, 0] is 1, which matches target1.[1] and [0, 0] are 1 and 0, matching target1 and target2.[1, 0] and [0] are 1 and 0, matching target1 and target2.Example 3:
Input: nums = [7], target1 = 1, target2 = 7
Output: 0
Explanation:
[7] is 7, which does not match target1, so no valid partition exists.
Constraints:
1 <= nums.length <= 1050 <= nums[i], target1, target2 <= 105target1 != target2Problem Overview: You are given an integer array and must count the number of ways to partition it into contiguous segments such that the XOR of adjacent segments alternates. Each partition splits the array into subarrays, and the XOR of those subarrays must follow an alternating pattern.
Approach 1: Brute Force Partition Enumeration (O(n^3) time, O(1) space)
The most direct method tries every possible partition configuration. For each pair of cut positions, compute the XOR of each segment and verify whether the XOR values alternate. This requires repeatedly computing subarray XOR values, which can take O(n) per check. With up to O(n^2) partitions and O(n) verification, the total complexity becomes O(n^3). While this approach is inefficient for large inputs, it clarifies the structure of the problem and highlights that segment XOR values are the only properties that matter.
Approach 2: Prefix XOR + Recurrence DP with Hash Table (O(n) time, O(n) space)
The key observation is that XOR of any subarray nums[l..r] can be computed using prefix XOR: px[r] ^ px[l-1]. Instead of recomputing XOR values for every partition, maintain a running prefix XOR while iterating through the array. Define a dynamic programming state where dp[i] represents the number of valid partitions ending at index i. The recurrence checks earlier positions where a cut can produce the required alternating XOR property.
A hash table stores counts of previously seen prefix XOR states that can extend a valid partition. For each index, compute the current prefix XOR and look up compatible previous states in O(1) time. This avoids scanning all previous indices. The XOR operation itself is constant time due to bit manipulation. Each element is processed once, producing an overall O(n) time solution with O(n) additional space for the DP array and hash map.
Recommended for interviews: Interviewers expect the prefix XOR + DP optimization. Starting with brute force shows you understand how partitions and XOR checks work. The optimized recurrence with a hash table demonstrates strong problem decomposition, efficient prefix computations, and familiarity with DP state transitions. This pattern—prefix XOR combined with hash lookups—appears frequently in XOR subarray and partition counting problems.
We define two hash tables cnt1 and cnt2, where cnt1[x] represents the number of partition schemes where the bitwise XOR result is x and the partition ends with target1, while cnt2[x] represents the number of partition schemes where the bitwise XOR result is x and the partition ends with target2. Initially, cnt2[0] = 1, representing an empty partition.
We use the variable pre to record the bitwise XOR result of the current prefix, and the variable ans to record the final answer. Then we traverse the array nums. For each element x, we update pre and calculate:
$
a = cnt2[pre \oplus target1]
b = cnt1[pre \oplus target2]
Then we update the answer:
ans = (a + b) \mod (10^9 + 7)
Next, we update the hash tables:
cnt1[pre] = (cnt1[pre] + a) \mod (10^9 + 7)
cnt2[pre] = (cnt2[pre] + b) \mod (10^9 + 7)
Finally, we return ans.
The time complexity is O(n), and the space complexity is O(n). Here, n$ is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Partition Enumeration | O(n^3) | O(1) | Useful for understanding the partition structure or validating small test cases. |
| Prefix XOR + DP with Hash Table | O(n) | O(n) | Best general solution for large arrays. Uses prefix XOR and hash lookups to count valid partitions efficiently. |
LeetCode BiWeekly Contest 174 | Number of Alternating XOR Partitions | 3811 Explained • DSA with Kumar K • 1,829 views views
Watch 3 more video solutions →Practice Number of Alternating XOR Partitions with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor