LeetCode Problem 3811

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Dynamic Programming, Bit Manipulation

Solution

LeetCode 3811 - Number of Alternating XOR Partitions

Problem Understanding

We are given an array nums and two distinct target XOR values, target1 and target2.

A partition divides the array into contiguous, non-empty blocks. Every element must belong to exactly one block, and the blocks must cover the entire array.

The partition is considered valid if the XOR value of the blocks alternates between the two targets:

• The first block must have XOR equal to target1.
• The second block must have XOR equal to target2.
• The third block must have XOR equal to target1.
• The fourth block must have XOR equal to target2.
• And so on.

The partition may contain any positive number of blocks. A partition consisting of a single block is valid if that block's XOR equals target1.

The task is to count how many valid partitions exist and return the result modulo 10^9 + 7.

The constraints are important:

• n = nums.length can be as large as 100,000.
• Values in the array and targets are at most 100,000.

Because the array can contain one hundred thousand elements, any algorithm that explicitly enumerates partitions is impossible. The number of possible partitions is already 2^(n-1) in the worst case.

Several edge cases deserve attention:

• A single-element array may or may not satisfy target1.
• Multiple different partition boundaries can produce identical prefix XOR values.
• Many valid partitions may exist, requiring modular arithmetic.
• The final block can be either a target1 block or a target2 block, depending on whether the total number of blocks is odd or even.
• Since target1 != target2, the alternating pattern is always well-defined.

Approaches

Brute Force

The most direct approach is to try every possible partition of the array.

There are n - 1 potential cut positions. Each position can either contain a cut or not contain a cut, producing 2^(n-1) possible partitions. For each partition, we can compute the XOR of every block and verify whether the sequence alternates between target1 and target2.

This approach is correct because it examines every possible partition and counts exactly those satisfying the rules.

Unfortunately, it is far too slow. Even for n = 50, the number of partitions becomes enormous. With n = 100,000, this approach is completely infeasible.

Key Insight

The XOR of a subarray can be computed using prefix XORs.

Let:

$$prefix[i] = nums[0] \oplus nums[1] \oplus \cdots \oplus nums[i-1]$$

Then the XOR of the subarray (j+1 ... i) is:

$$prefix[i] \oplus prefix[j]$$

Suppose we want a block ending at position i whose XOR equals target1.

Then we need:

$$prefix[i] \oplus prefix[j] = target1$$

which implies:

$$prefix[j] = prefix[i] \oplus target1$$

Therefore, instead of checking all previous positions individually, we only need to know how many valid partitions end at positions whose prefix XOR equals a specific value.

This suggests dynamic programming combined with hash tables.

We maintain:

• Partitions whose last block XOR is target1
• Partitions whose last block XOR is target2

Hash maps allow us to instantly find all compatible previous partition endpoints.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n · n)	O(n)	Enumerates all partitions
Optimal	O(n)	O(n)	Prefix XOR + DP + hash maps

Algorithm Walkthrough

State Definition

Let:

• A[i] = number of valid partitions ending at position i whose last block XOR is target1
• B[i] = number of valid partitions ending at position i whose last block XOR is target2

Since we only need aggregated information grouped by prefix XOR value, we do not store all states explicitly.

Instead we maintain:

• mapA[x] = sum of all A[j] where prefix[j] = x
• mapB[x] = sum of all B[j] where prefix[j] = x

Step-by-Step Procedure

1. Compute prefix XOR incrementally while scanning the array.
2. For the current position i, let the current prefix XOR be px.
3. Compute the number of ways to end with a target1 block.

A block from the beginning of the array is valid if:

$$px = target1$$

This contributes one partition.

We can also append a target1 block after a partition ending with target2.

We need:

$$prefix[j] = px \oplus target1$$

Therefore:

$$A = [px = target1] + mapB[px \oplus target1]$$ 4. Compute the number of ways to end with a target2 block.

A target2 block must come after a partition ending with target1.

Again:

$$prefix[j] = px \oplus target2$$

Hence:

$$B = mapA[px \oplus target2]$$ 5. Store these newly computed values into the hash maps:

• mapA[px] += A
• mapB[px] += B

6. Continue until the end of the array.
7. At the final position, the answer is:

$$A[n] + B[n]$$

because the partition may contain either an odd or even number of blocks.

Why it Works

The key invariant is that mapA and mapB always contain the total number of valid partitions ending at previously processed positions, grouped by prefix XOR value.

Whenever we want a new block with XOR equal to a target value, the prefix XOR identity uniquely determines which previous endpoints are compatible. The hash maps instantly provide the total count of all such endpoints. Every valid partition is counted exactly once when its final block is created, and every counted partition satisfies the alternating requirement by construction.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def alternatingXOR(self, nums: List[int], target1: int, target2: int) -> int:
        MOD = 10**9 + 7

        map_a = defaultdict(int)
        map_b = defaultdict(int)

        prefix_xor = 0
        last_a = 0
        last_b = 0

        for num in nums:
            prefix_xor ^= num

            ways_a = (1 if prefix_xor == target1 else 0)
            ways_a += map_b[prefix_xor ^ target1]

            ways_b = map_a[prefix_xor ^ target2]

            ways_a %= MOD
            ways_b %= MOD

            map_a[prefix_xor] = (map_a[prefix_xor] + ways_a) % MOD
            map_b[prefix_xor] = (map_b[prefix_xor] + ways_b) % MOD

            last_a = ways_a
            last_b = ways_b

        return (last_a + last_b) % MOD

The implementation follows the dynamic programming recurrence directly.

prefix_xor tracks the current prefix XOR. For every position, we calculate the number of partitions whose final block is a target1 block and the number whose final block is a target2 block.

map_a stores aggregated counts of states ending with target1, grouped by prefix XOR. Similarly, map_b stores aggregated counts of states ending with target2.

After computing the current state, we immediately insert it into the corresponding map so future positions can extend it. The variables last_a and last_b always hold the states for the current array position. Once the scan finishes, they represent the states at the final index, and their sum is the answer.

Go Solution

func alternatingXOR(nums []int, target1 int, target2 int) int {
	const MOD int = 1000000007

	mapA := make(map[int]int)
	mapB := make(map[int]int)

	prefixXor := 0
	lastA := 0
	lastB := 0

	for _, num := range nums {
		prefixXor ^= num

		waysA := 0
		if prefixXor == target1 {
			waysA = 1
		}
		waysA = (waysA + mapB[prefixXor^target1]) % MOD

		waysB := mapA[prefixXor^target2] % MOD

		mapA[prefixXor] = (mapA[prefixXor] + waysA) % MOD
		mapB[prefixXor] = (mapB[prefixXor] + waysB) % MOD

		lastA = waysA
		lastB = waysB
	}

	return (lastA + lastB) % MOD
}

The Go implementation mirrors the Python version. Go maps return zero for missing keys, which naturally matches the recurrence. All updates are performed modulo 10^9 + 7 to prevent overflow and satisfy the problem requirements.

Worked Examples

Example 1

Input

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

Prefix XOR sequence:

Position	Prefix XOR
1	2
2	1
3	0
4	4

Processing:

i	px	waysA	waysB
1	2	0	0
2	1	1	0
3	0	0	0
4	4	0	1

At the final position:

waysA + waysB = 1

Answer:

1

Example 2

Input

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

Prefix XOR sequence:

Position	Prefix XOR
1	1
2	1
3	1

Processing:

i	px	waysA	waysB
1	1	1	0
2	1	1	1
3	1	1	2

Final answer:

1 + 2 = 3

The three valid partitions are:

[1,0,0]
[1] [0,0]
[1,0] [0]

Example 3

Input

nums = [7]
target1 = 1
target2 = 7

Processing:

i	px	waysA	waysB
1	7	0	0

Final answer:

0

No valid partition exists.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed once, every hash map operation is O(1) average
Space	O(n)	Up to one stored entry per distinct prefix XOR occurrence

The algorithm performs a single linear scan of the array. Every iteration executes a constant amount of work and a constant number of hash map accesses. The hash maps store aggregated counts indexed by prefix XOR values, yielding linear space usage in the worst case.

Test Cases

sol = Solution()

assert sol.alternatingXOR([2, 3, 1, 4], 1, 5) == 1  # example 1
assert sol.alternatingXOR([1, 0, 0], 1, 0) == 3     # example 2
assert sol.alternatingXOR([7], 1, 7) == 0           # example 3

assert sol.alternatingXOR([1], 1, 0) == 1           # single valid block
assert sol.alternatingXOR([1], 0, 1) == 0           # single invalid block

assert sol.alternatingXOR([0, 0], 0, 1) == 2        # two possible valid partitions
assert sol.alternatingXOR([5, 5], 0, 1) == 1        # whole array XOR is target1

assert sol.alternatingXOR([1, 1, 1, 1], 0, 1) == 3 # repeated prefix XOR values
assert sol.alternatingXOR([0, 0, 0], 0, 1) == 4    # many valid partitions

assert sol.alternatingXOR([3, 3, 3], 3, 0) > 0     # alternating extensions exist

Test Summary

Test	Why
[2,3,1,4]	Official example 1
[1,0,0]	Official example 2
[7]	Official example 3
Single valid element	Smallest successful input
Single invalid element	Smallest failing input
[0,0]	Multiple valid partitions
[5,5]	Whole-array partition only
Repeated prefix XORs	Verifies hash map aggregation
[0,0,0]	Large number of valid partitions
[3,3,3]	Alternating transitions across states

Edge Cases

Single-Block Partition

A common mistake is to assume every valid partition must contain at least two blocks. The problem explicitly allows a single block. If the XOR of the entire prefix up to the current position equals target1, we must count that partition directly. The implementation handles this through the term:

1 if prefix_xor == target1 else 0

which represents starting from the beginning of the array.

Repeated Prefix XOR Values

Different positions can have identical prefix XOR values. A naive implementation might overwrite previous information and lose valid partitions. The hash maps store cumulative counts rather than a single state, ensuring that every compatible previous endpoint contributes to future transitions.

Large Numbers of Partitions

The number of valid partitions can grow exponentially with the array length. Without modular arithmetic, integer values could become extremely large. Every update is performed modulo 10^9 + 7, guaranteeing correctness and preventing overflow issues.

Final Block Can Be Either Target

The alternating sequence always starts with target1, but it does not need to end with target1. A valid partition may contain either an odd or even number of blocks. Therefore, the final answer is the sum of both terminal states:

last_a + last_b

This correctly counts partitions ending in either target value.