110. Matching XOR Triplets
A telemetry log nums holds non-negative integers. Pick three indices i < j <= k. They cut a piece of the log into a left part nums[i..j-1] and a right part nums[j..k], both contiguous and non-empty. The cut is balanced when the bitwise XOR of all values in the left part equals the bitwise XOR of all values in the right part.
Count every triple (i, j, k) with 0 <= i < j <= k < n that gives a balanced cut. Triples are distinguished by their indices. The count can be enormous, so return it modulo 1000000007.
Example 1
- Input:
- nums = [2,3,1,6,7]
- Output:
- 4
- Explanation:
Four balanced triples exist; one is i=0, j=2, k=2, where the left part [2,3] and the right part [1] both XOR to 1.
Example 2
- Input:
- nums = [4,4,4]
- Output:
- 2
- Explanation:
Only cuts with a single 4 on each side balance: (i,j,k) = (0,1,1) and (1,2,2).
Example 3
- Input:
- nums = [1,2,3]
- Output:
- 2
- Explanation:
Two cuts balance: left [1] against right [2,3] (both XOR 1), and left [1,2] against right [3] (both XOR 3).
Constraints
1 ≤ nums.length ≤ 105
0 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)