Skip to content

3811. Number of Alternating XOR Partitions

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.

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

Solutions

Solution 1: Recurrence

We define two hash tables \(\textit{cnt1}\) and \(\textit{cnt2}\), where \(\textit{cnt1}[x]\) represents the number of partition schemes where the bitwise XOR result is \(x\) and the partition ends with \(\textit{target1}\), while \(\textit{cnt2}[x]\) represents the number of partition schemes where the bitwise XOR result is \(x\) and the partition ends with \(\textit{target2}\). Initially, \(\textit{cnt2}[0] = 1\), representing an empty partition.

We use the variable \(\textit{pre}\) to record the bitwise XOR result of the current prefix, and the variable \(\textit{ans}\) to record the final answer. Then we traverse the array \(\textit{nums}\). For each element \(x\), we update \(\textit{pre}\) and calculate:

\[ a = \textit{cnt2}[\textit{pre} \oplus \textit{target1}] \]
\[ b = \textit{cnt1}[\textit{pre} \oplus \textit{target2}] \]

Then we update the answer:

\[ \textit{ans} = (a + b) \mod (10^9 + 7) \]

Next, we update the hash tables:

\[ \textit{cnt1}[\textit{pre}] = (\textit{cnt1}[\textit{pre}] + a) \mod (10^9 + 7) \]
\[ \textit{cnt2}[\textit{pre}] = (\textit{cnt2}[\textit{pre}] + b) \mod (10^9 + 7) \]

Finally, we return \(\textit{ans}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def alternatingXOR(self, nums: List[int], target1: int, target2: int) -> int:
        cnt1 = defaultdict(int)
        cnt2 = defaultdict(int)
        cnt2[0] = 1
        ans = pre = 0
        mod = 10**9 + 7
        for x in nums:
            pre ^= x
            a = cnt2[pre ^ target1]
            b = cnt1[pre ^ target2]
            ans = (a + b) % mod
            cnt1[pre] = (cnt1[pre] + a) % mod
            cnt2[pre] = (cnt2[pre] + b) % mod
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int alternatingXOR(int[] nums, int target1, int target2) {
        final int mod = (int) 1e9 + 7;

        Map<Integer, Integer> cnt1 = new HashMap<>();
        Map<Integer, Integer> cnt2 = new HashMap<>();
        cnt2.put(0, 1);

        int ans = 0;
        int pre = 0;
        for (int x : nums) {
            pre ^= x;
            int a = cnt2.getOrDefault(pre ^ target1, 0);
            int b = cnt1.getOrDefault(pre ^ target2, 0);
            ans = (a + b) % mod;
            cnt1.put(pre, (cnt1.getOrDefault(pre, 0) + a) % mod);
            cnt2.put(pre, (cnt2.getOrDefault(pre, 0) + b) % mod);
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int alternatingXOR(vector<int>& nums, int target1, int target2) {
        const int MOD = 1e9 + 7;
        unordered_map<int, int> cnt1, cnt2;
        cnt2[0] = 1;

        int pre = 0, ans = 0;
        for (int x : nums) {
            pre ^= x;
            int a = cnt2[pre ^ target1];
            int b = cnt1[pre ^ target2];
            ans = (a + b) % MOD;
            cnt1[pre] = (cnt1[pre] + a) % MOD;
            cnt2[pre] = (cnt2[pre] + b) % MOD;
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func alternatingXOR(nums []int, target1 int, target2 int) int {
    mod := 1_000_000_007
    cnt1 := make(map[int]int)
    cnt2 := make(map[int]int)
    cnt2[0] = 1

    pre := 0
    ans := 0

    for _, x := range nums {
        pre ^= x
        a := cnt2[pre^target1]
        b := cnt1[pre^target2]
        ans = (a + b) % mod
        cnt1[pre] = (cnt1[pre] + a) % mod
        cnt2[pre] = (cnt2[pre] + b) % mod
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function alternatingXOR(nums: number[], target1: number, target2: number): number {
    const MOD = 1_000_000_007;
    const cnt1 = new Map<number, number>();
    const cnt2 = new Map<number, number>();
    cnt2.set(0, 1);

    let pre = 0;
    let ans = 0;

    for (const x of nums) {
        pre ^= x;
        const a = cnt2.get(pre ^ target1) ?? 0;
        const b = cnt1.get(pre ^ target2) ?? 0;
        ans = (a + b) % MOD;
        cnt1.set(pre, ((cnt1.get(pre) ?? 0) + a) % MOD);
        cnt2.set(pre, ((cnt2.get(pre) ?? 0) + b) % MOD);
    }

    return ans;
}

Comments