3811. Number of Alternating XOR Partitions

MediumBit ManipulationArrayHash TableDynamic Programming

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem 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. In other words, you divide the array into consecutive groups, where each group contains at least one element, and every element belongs to exactly one group.

A partition is considered valid if the bitwise XOR of the elements in each block alternates between target1 and target2, starting with target1.

Concretely, if the blocks are b1, b2, b3, ..., then:

XOR(b1) = target1 — the XOR of all elements in the first block must equal target1.
XOR(b2) = target2 — the XOR of all elements in the second block (if it exists) must equal target2.
XOR(b3) = target1 — the XOR of all elements in the third block (if it exists) must equal target1, and so on.

The XOR results of consecutive blocks keep switching between target1 and target2, with the very first block required to be target1.

Your task is to count how many valid partitions of nums exist, and return that count modulo 10^9 + 7.

Note: A partition consisting of a single block is valid as long as its XOR equals target1.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

Counting valid partitions where block XORs alternate between target1 and target2 uses prefix XOR with DP tracking of state transitions.

Open in Flowchart

Intuition

The key observation is that the XOR of a contiguous block can be expressed using prefix XOR. If we let pre[i] denote the XOR of the first i elements, then the XOR of a block spanning from index j+1 to i equals pre[i] ^ pre[j]. So whenever we want a block to have XOR equal to some value t, we need pre[i] ^ pre[j] = t, which means pre[j] = pre[i] ^ t.

This turns the problem into a counting task: as we scan the array and maintain the running prefix XOR pre, we want to know how many earlier positions j could serve as the start boundary of the current block so that the block's XOR matches the required target.

But there's a twist — the required target alternates between target1 and target2 depending on whether the current block is in an "odd" position (1st, 3rd, ...) or an "even" position (2nd, 4th, ...). To handle this alternation, we track partitions by what their last block's XOR was:

cnt1[x] counts the number of valid partitions that end at some position with prefix XOR x, where the last block's XOR was target1.
cnt2[x] counts the number of valid partitions ending at prefix XOR x, where the last block's XOR was target2.

The starting state is cnt2[0] = 1. This represents the "empty" partition before any elements: pretending the block before the first real block ended with target2 lets the first real block correctly be a target1 block, keeping the alternation consistent.

Now, at each position with prefix XOR pre, we consider closing off a new block here:

If this new block should have XOR target1, the previous block must have ended with target2. The block's XOR is pre ^ pre[j] = target1, so pre[j] = pre ^ target1. The number of ways is a = cnt2[pre ^ target1].
If this new block should have XOR target2, the previous block must have ended with target1. Similarly, pre[j] = pre ^ target2, giving b = cnt1[pre ^ target2].

Every valid partition counted in a now ends with a target1 block, so we add a into cnt1[pre]. Likewise, b partitions now end with a target2 block, so we add b into cnt2[pre].

The answer is the number of valid partitions that cover the entire array ending at the final position, which is exactly a + b computed at the last element. Because the recurrence requires the first block to be target1 (enforced by the cnt2[0] = 1 seed) and naturally alternates afterward, every counted partition respects the required pattern.

Pattern Learn more about Dynamic Programming patterns.

Solution Approach

Solution 1: Recurrence

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 ^ target1]

b = cnt1[pre ^ target2]

Then we update the answer:

ans = (a + b) % (10^9 + 7)

Next, we update the hash tables:

cnt1[pre] = (cnt1[pre] + a) % (10^9 + 7)

cnt2[pre] = (cnt2[pre] + b) % (10^9 + 7)

Finally, we return ans.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums. This is because we traverse the array once, and for each element we perform constant-time hash table lookups and updates, while the hash tables may store up to O(n) distinct prefix XOR values.

Example Walkthrough

Let's walk through a small example to see how the recurrence works in practice.

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

First, let's understand what we're looking for. We want to count partitions where the block XORs alternate 3, 0, 3, 0, ... starting with 3.

Let's compute the prefix XORs to keep handy:

pre[0] = 0 (empty prefix)
After element 1: pre = 0 ^ 1 = 1
After element 2: pre = 1 ^ 2 = 3
After element 3: pre = 3 ^ 3 = 0

Initialization:

cnt1 = {}
cnt2 = {0: 1} (the seed, representing the empty partition that "ended with target2")
pre = 0, ans = 0

Step 1 — process x = 1:

Update pre = 0 ^ 1 = 1.

a = cnt2[pre ^ target1] = cnt2[1 ^ 3] = cnt2[2] = 0 (Looking for a block ending here with XOR = 3, whose start boundary has prefix 2. None exist.)
b = cnt1[pre ^ target2] = cnt1[1 ^ 0] = cnt1[1] = 0 (Looking for a block ending here with XOR = 0, preceded by a target1 block. None exist.)

ans = (0 + 0) = 0

Update tables:

cnt1[1] += 0 → cnt1 = {}
cnt2[1] += 0 → cnt2 = {0: 1}

Step 2 — process x = 2:

Update pre = 1 ^ 2 = 3.

a = cnt2[pre ^ target1] = cnt2[3 ^ 3] = cnt2[0] = 1 (A target1 block from the start to here has XOR 3 ^ 0 = 3. The seed cnt2[0]=1 confirms this is a valid first block.)
b = cnt1[pre ^ target2] = cnt1[3 ^ 0] = cnt1[3] = 0

ans = (1 + 0) = 1

Update tables:

cnt1[3] += 1 → cnt1 = {3: 1} (one partition ending here, last block XOR = target1)
cnt2[3] += 0 → cnt2 = {0: 1}

So far we've found: [1, 2] | ... where block [1,2] has XOR 3. This corresponds to the partition [[1,2], ...].

Step 3 — process x = 3:

Update pre = 3 ^ 3 = 0.

a = cnt2[pre ^ target1] = cnt2[0 ^ 3] = cnt2[3] = 0 (No target2-ending partition with prefix 3 exists.)
b = cnt1[pre ^ target2] = cnt1[0 ^ 0] = cnt1[0] = 0 (Wait — we need a previous target1 block ending at prefix 0. cnt1[0] is empty.)

Hmm, ans = (0 + 0) = 0 at this step.

Final answer: ans = 0

Let's verify by brute force. The possible partitions of [1, 2, 3] and their block XORs:

[1] | [2] | [3] → XORs 1, 2, 3 — first block must be 3, but it's 1. ✗
[1] | [2, 3] → XORs 1, 1 — first block 1 ≠ 3. ✗
[1, 2] | [3] → XORs 3, 3 — first is 3 ✓, but second must be 0, it's 3. ✗
[1, 2, 3] → XOR 0 — must be 3, but it's 0. ✗

No valid partition exists, confirming ans = 0. ✓

A quick note on how ans gets captured correctly: the answer is the value of a + b computed at the last element, because that is precisely the count of partitions ending exactly at the final index (covering the whole array). Intermediate a + b values describe partitions ending early, which are folded into cnt1/cnt2 to be extended later — they are not the final answer unless they land on the last position.

To see a non-zero outcome, consider tweaking to target1 = 3, target2 = 3 — but since the problem requires target1 and target2 to be distinct, the seed/alternation logic guarantees the strict 3, 0, 3, 0... pattern is always enforced.

Solution Implementation

1from collections import defaultdict
2from typing import List
3
4
5class Solution:
6    def alternatingXOR(self, nums: List[int], target1: int, target2: int) -> int:
7        # count_need_t1[p]: number of prefixes ending at value p that currently
8        #   expect `target1` to be matched next.
9        # count_need_t2[p]: number of prefixes ending at value p that currently
10        #   expect `target2` to be matched next.
11        count_need_t1: defaultdict[int, int] = defaultdict(int)
12        count_need_t2: defaultdict[int, int] = defaultdict(int)
13
14        # Seed: the empty prefix (XOR == 0) is available and expects target1 first
15        # (it lives in the t2 map so that `pre ^ target1` lookups can find it).
16        count_need_t2[0] = 1
17
18        answer = 0
19        prefix_xor = 0
20        MOD = 10**9 + 7
21
22        for value in nums:
23            # Extend the running prefix XOR with the current element.
24            prefix_xor ^= value
25
26            # Number of earlier prefixes that, combined with the current prefix,
27            # produce a segment XOR equal to target1 (resp. target2).
28            ways_from_t1 = count_need_t2[prefix_xor ^ target1]
29            ways_from_t2 = count_need_t1[prefix_xor ^ target2]
30
31            # NOTE: this assignment overwrites `answer` each step (matches the
32            # original code, which used `=` rather than `+=`).
33            answer = (ways_from_t1 + ways_from_t2) % MOD
34
35            # Register the current prefix into both maps, propagating the counts
36            # so future elements can chain onto these subarrays (alternation).
37            count_need_t1[prefix_xor] = (count_need_t1[prefix_xor] + ways_from_t1) % MOD
38            count_need_t2[prefix_xor] = (count_need_t2[prefix_xor] + ways_from_t2) % MOD
39
40        return answer
41

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    public int alternatingXOR(int[] nums, int target1, int target2) {
6        // Modulus value to prevent integer overflow on large counts
7        final int MOD = (int) 1e9 + 7;
8
9        // countOdd: stores how many subsequences end at a given prefix XOR
10        //           where the last "step" used target2 (odd-position transitions)
11        // countEven: stores how many subsequences end at a given prefix XOR
12        //            where the last "step" used target1 (even-position transitions)
13        Map<Integer, Integer> countOdd = new HashMap<>();
14        Map<Integer, Integer> countEven = new HashMap<>();
15
16        // Initialize with an empty prefix (XOR = 0) representing the base state
17        countEven.put(0, 1);
18
19        int answer = 0;
20
21        // prefixXor accumulates the XOR of all elements processed so far
22        int prefixXor = 0;
23
24        for (int value : nums) {
25            // Update the running prefix XOR with the current element
26            prefixXor ^= value;
27
28            // Number of valid subsequences that can extend using target1:
29            // a previous "even" state combined with current prefix matching target1
30            int extendWithTarget1 = countEven.getOrDefault(prefixXor ^ target1, 0);
31
32            // Number of valid subsequences that can extend using target2:
33            // a previous "odd" state combined with current prefix matching target2
34            int extendWithTarget2 = countOdd.getOrDefault(prefixXor ^ target2, 0);
35
36            // The current answer is the total number of valid combinations
37            answer = (extendWithTarget1 + extendWithTarget2) % MOD;
38
39            // Record this prefix as a new "odd" state, carrying over the target1 extensions
40            countOdd.put(prefixXor,
41                    (countOdd.getOrDefault(prefixXor, 0) + extendWithTarget1) % MOD);
42
43            // Record this prefix as a new "even" state, carrying over the target2 extensions
44            countEven.put(prefixXor,
45                    (countEven.getOrDefault(prefixXor, 0) + extendWithTarget2) % MOD);
46        }
47
48        return answer;
49    }
50}
51

1class Solution {
2public:
3    int alternatingXOR(vector<int>& nums, int target1, int target2) {
4        const int kMod = 1e9 + 7;
5
6        // countEven[v]: number of ways a chain ends at prefix value v
7        //              after matching an even number of segments (next match uses target1).
8        // countOdd[v] : number of ways a chain ends at prefix value v
9        //              after matching an odd number of segments (next match uses target2).
10        unordered_map<int, int> countOdd, countEven;
11
12        // Base case: the empty prefix (XOR == 0) is a valid starting point
13        // for matching the first segment against target1.
14        countEven[0] = 1;
15
16        int prefixXor = 0;  // running XOR of nums[0..i]
17        int answer = 0;
18
19        for (int x : nums) {
20            // Extend the running prefix XOR with the current element.
21            prefixXor ^= x;
22
23            // A segment XOR equals target1 when some earlier prefix value
24            // equals (prefixXor ^ target1); such states live in countEven.
25            int fromEven = countEven[prefixXor ^ target1];
26
27            // A segment XOR equals target2 when some earlier prefix value
28            // equals (prefixXor ^ target2); such states live in countOdd.
29            int fromOdd = countOdd[prefixXor ^ target2];
30
31            // The total ways to reach the current position is the sum of both.
32            answer = (fromEven + fromOdd) % kMod;
33
34            // Matching a target1 segment moves an even-state chain to an odd-state
35            // chain ending at the current prefix value.
36            countOdd[prefixXor] = (countOdd[prefixXor] + fromEven) % kMod;
37
38            // Matching a target2 segment moves an odd-state chain to an even-state
39            // chain ending at the current prefix value.
40            countEven[prefixXor] = (countEven[prefixXor] + fromOdd) % kMod;
41        }
42
43        return answer;
44    }
45};
46

1// Modulo constant to keep counts within safe integer range.
2const MOD = 1_000_000_007;
3
4/**
5 * Counts weighted alternating-XOR subsequence combinations.
6 *
7 * The algorithm walks a running prefix XOR (`prefixXor`) over `nums`.
8 * Two maps store accumulated, weighted counts of previously seen prefix
9 * XOR values. They alternate roles so that matches toggle between
10 * `target1` and `target2`, producing an alternating XOR pattern.
11 *
12 * @param nums    - Input array of numbers.
13 * @param target1 - First XOR target used for one phase of the alternation.
14 * @param target2 - Second XOR target used for the other phase.
15 * @returns The result value (mod 1e9+7) associated with the final element.
16 */
17function alternatingXOR(nums: number[], target1: number, target2: number): number {
18    // Map of prefix-XOR values weighted by how many target2-style matches reached them.
19    const countTarget1 = new Map<number, number>();
20
21    // Map of prefix-XOR values weighted by how many target1-style matches reached them.
22    // Seeded with {0: 1} to represent the empty prefix (XOR of nothing is 0).
23    const countTarget2 = new Map<number, number>();
24    countTarget2.set(0, 1);
25
26    // Running XOR of all elements processed so far.
27    let prefixXor = 0;
28
29    // Holds the result; reassigned each iteration so it reflects the final element.
30    let answer = 0;
31
32    for (const value of nums) {
33        // Extend the prefix XOR with the current element.
34        prefixXor ^= value;
35
36        // Number of prior prefixes that pair with the current one via target1.
37        const matchedViaTarget1 = countTarget2.get(prefixXor ^ target1) ?? 0;
38
39        // Number of prior prefixes that pair with the current one via target2.
40        const matchedViaTarget2 = countTarget1.get(prefixXor ^ target2) ?? 0;
41
42        // Combine both alternation phases for this position.
43        answer = (matchedViaTarget1 + matchedViaTarget2) % MOD;
44
45        // Feed the target1 matches into countTarget1 so the next phase can build on them.
46        countTarget1.set(
47            prefixXor,
48            ((countTarget1.get(prefixXor) ?? 0) + matchedViaTarget1) % MOD,
49        );
50
51        // Feed the target2 matches into countTarget2 so the next phase can build on them.
52        countTarget2.set(
53            prefixXor,
54            ((countTarget2.get(prefixXor) ?? 0) + matchedViaTarget2) % MOD,
55        );
56    }
57
58    return answer;
59}
60

Time and Space Complexity

Time Complexity: O(n). The code iterates through the array nums exactly once with a single for loop. For each element x, it performs a constant number of operations: an XOR update on pre, two dictionary lookups (cnt2[pre ^ target1] and cnt1[pre ^ target2]), one addition for ans, and two dictionary updates (cnt1[pre] and cnt2[pre]). Since each of these operations takes O(1) average time, the total time complexity is O(n), where n is the length of the array nums.
Space Complexity: O(n). The code uses two hash tables cnt1 and cnt2 (implemented as defaultdict) to record the cumulative counts associated with each prefix XOR value pre. In the worst case, each prefix XOR value is distinct, so these dictionaries can store up to O(n) entries in total. The remaining variables (ans, pre, mod, a, b) only occupy constant space. Therefore, the overall space complexity is O(n), where n is the length of the array nums.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Overwriting `answer` with `=` instead of accumulating with `+=`

The most dangerous trap in this code is the line:

answer = (ways_from_t1 + ways_from_t2) % MOD

This overwrites answer on every iteration. The final returned value therefore only reflects the ways computed at the last element, not the total across all valid partitions.

Why this is wrong: A valid partition must cover the entire array, so it always ends at the final index. At first glance, "only counting at the last step" seems correct. But ways_from_t1 / ways_from_t2 at the last position count all valid partitions that end exactly at the last element — which is indeed every valid partition. So the = happens to work only because every valid partition terminates at the final element.

The pitfall is conceptual: this is fragile and confusing. If the problem were slightly altered (e.g., "count valid partitions of every prefix"), the = would silently produce wrong results. The intent is far clearer—and more robust—if you explicitly capture the answer after the loop:

for value in nums:
    prefix_xor ^= value
    ways_from_t1 = count_need_t2[prefix_xor ^ target1]
    ways_from_t2 = count_need_t1[prefix_xor ^ target2]
    count_need_t1[prefix_xor] = (count_need_t1[prefix_xor] + ways_from_t1) % MOD
    count_need_t2[prefix_xor] = (count_need_t2[prefix_xor] + ways_from_t2) % MOD

# The answer is exactly the ways recorded at the final prefix that
# legitimately end a partition (those that just matched target1 or target2).
answer = (count_need_t1[prefix_xor] + count_need_t2[prefix_xor]) % MOD  # see note below

Note: If you accumulate into the maps as above, you must be careful: count_need_t1[prefix_xor] could include contributions from earlier prefixes that share the same XOR value. The cleanest fix is to keep the per-step value in a local variable and store it as the answer at the last iteration:

answer = 0
for i, value in enumerate(nums):
    prefix_xor ^= value
    ways = (count_need_t2[prefix_xor ^ target1] + count_need_t1[prefix_xor ^ target2]) % MOD
    ...
    if i == len(nums) - 1:
        answer = ways

Pitfall 2: Misunderstanding the seed `count_need_t2[0] = 1`

It is tempting to seed count_need_t1[0] = 1 instead, reasoning "we start by expecting target1." This is backwards and produces zero or wrong answers.

Why: The lookups are

ways_from_t1 = count_need_t2[prefix_xor ^ target1]   # block XOR == target1
ways_from_t2 = count_need_t1[prefix_xor ^ target2]   # block XOR == target2

The empty prefix (XOR = 0) represents "no block placed yet," and the next block must equal target1. A block from prefix j to prefix i has XOR pre[i] ^ pre[j]. For that to equal target1, we need pre[j] = pre[i] ^ target1, which is the value we look up in count_need_t2. Hence the empty prefix must live in count_need_t2 so the first block (the one yielding target1) can find it. Seeding the wrong map breaks the very first block match.

Pitfall 3: Forgetting the modulo on intermediate updates

Both count_need_t1[prefix_xor] and count_need_t2[prefix_xor] can grow combinatorially. Applying % MOD only to answer but not to the map updates causes the counts to overflow into huge integers (slow in Python, incorrect in fixed-width languages). Always apply % MOD at every accumulation step, exactly as the code does.

Pitfall 4: Assuming `target1 != target2` is guaranteed but not exploiting it

The problem guarantees the targets are distinct, and the algorithm relies on this. If target1 == target2, a single block could simultaneously satisfy both "needs," and the two maps would double-count, breaking the alternation logic. While the constraint protects you here, a defensive solution should not silently assume distinctness when adapting this code to a variant problem—add an explicit check or document the assumption clearly.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering