109. XOR Stretches
A signal recorder stores non-negative integer samples in nums. Combining a contiguous stretch of samples means taking the bitwise XOR of every value inside it. Given a target integer k, count how many non-empty contiguous stretches of nums combine to exactly k.
Stretches are told apart by their positions, so two stretches with identical contents at different places are counted separately. Because of the constraints on n, the answer always fits in a 32-bit signed integer.
Example 1
- Input:
- nums = [1,2,3,1,2], k = 3
- Output:
- 4
- Explanation:
Four stretches XOR to 3: [1,2] at positions 0-1, [3] at position 2, [1,2] at positions 3-4, and the whole array.
Example 2
- Input:
- nums = [3,3,3], k = 0
- Output:
- 2
- Explanation:
Only the stretch [3,3] XORs to 0, and it can start at position 0 or 1, giving 2.
Example 3
- Input:
- nums = [8,8,8,8], k = 8
- Output:
- 6
- Explanation:
Stretches of odd length XOR to 8: four of length 1 and two of length 3, so the answer is 6.
Constraints
1 ≤ nums.length ≤ 60000
0 ≤ nums[i], k ≤ 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)