Watch 4 video solutions for Number of Alternating XOR Partitions, a medium level problem involving Array, Hash Table, Dynamic Programming. This walkthrough by DSA with Kumar K has 1,829 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |