Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  }
  
  

• 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;
      }
  };
  
  

• 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
  
  

• 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
  }
  
  

• 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;
  }
  
  

All Problems

All Solutions