Skip to main content
Talentd

Number of Alternating XOR Partitions - Solution & Explanation

MediumArrayHash TableDynamic ProgrammingBit Manipulation10 min read
Practice this problem

Problem Statement

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.

 

Example 1:

Input: nums = [2,3,1,4], target1 = 1, target2 = 5

Output: 1

Explanation:​​​​​​​

  • The XOR of [2, 3] is 1, which matches target1.
  • The XOR of the remaining block [1, 4] is 5, which matches target2.
  • This is the only valid alternating partition, so the answer is 1.

Example 2:

Input: nums = [1,0,0], target1 = 1, target2 = 0

Output: 3

Explanation:

  • ​​​​​​​The XOR of [1, 0, 0] is 1, which matches target1.
  • The XOR of [1] and [0, 0] are 1 and 0, matching target1 and target2.
  • The XOR of [1, 0] and [0] are 1 and 0, matching target1 and target2.
  • Thus, the answer is 3.​​​​​​​

Example 3:

Input: nums = [7], target1 = 1, target2 = 7

Output: 0

Explanation:

  • The XOR of [7] is 7, which does not match target1, so no valid partition exists.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i], target1, target2 <= 105
  • target1 != target2

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Partition EnumerationO(n^3)O(1)Useful for understanding the partition structure or validating small test cases.
Prefix XOR + DP with Hash TableO(n)O(n)Best general solution for large arrays. Uses prefix XOR and hash lookups to count valid partitions efficiently.

Video Solution

LeetCode BiWeekly Contest 174 | Number of Alternating XOR Partitions | 3811 Explained • DSA with Kumar K • 1,941 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Number of Alternating XOR Partitions easy or hard?
The problem is typically rated Medium because it requires combining multiple ideas: prefix XOR, dynamic programming over partitions, and hash table optimization. Once the prefix XOR property is recognized, the recurrence becomes straightforward.
Number of Alternating XOR Partitions Python/Java solution
Implement the recurrence using a prefix XOR variable and a dictionary or HashMap that tracks counts of relevant states. Update dp values as you iterate through the array. The same logic translates directly across Python, Java, C++, Go, and TypeScript since all support constant-time hash map operations.
How to solve Number of Alternating XOR Partitions in O(n)?
Maintain a running prefix XOR while iterating through the array. Define a DP state where dp[i] counts the number of valid partitions ending at index i. Use a hash table to store previously seen prefix XOR states so you can quickly determine how many earlier partitions can extend to the current position while preserving the alternating XOR condition.
What is the best approach for Number of Alternating XOR Partitions?
The most efficient approach uses prefix XOR combined with dynamic programming and a hash table. Prefix XOR allows constant-time computation of any subarray XOR, while the DP recurrence counts valid partitions ending at each index. A hash map tracks compatible previous states, reducing the overall complexity to O(n) time with O(n) space.
Is Number of Alternating XOR Partitions asked at Google/Amazon/Meta?
Problems involving prefix XOR, partition counting, and hash table optimizations frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of XOR subarray counting and dynamic programming over partitions are common in mid‑level algorithm interviews.
What data structure is used in Number of Alternating XOR Partitions?
The core data structures are arrays for prefix XOR and dynamic programming, plus a hash table for fast lookup of previously seen XOR states. Bit manipulation through the XOR operation enables constant-time subarray XOR calculations.
What is the time complexity of Number of Alternating XOR Partitions?
The optimal solution runs in O(n) time and O(n) space. Each array element is processed once while maintaining prefix XOR values and updating dynamic programming states through constant-time hash table lookups.

Ready to solve this problem?

Practice Number of Alternating XOR Partitions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays