Balanced XOR Splits
MediumBit Manipulation
Problem
A stream of packets packets is cut into a left part packets[i..j-1] and an adjacent right part packets[j..k], where 0 ≤ i < j ≤ k < n. The cut is balanced when the XOR of the left part equals the XOR of the right part.
Return the number of balanced triples (i, j, k).
Example 1
- Input:
- packets = [6, 6, 6]
- Output:
- 2
(0, 1, 1): 6 vs 6, and (1, 2, 2): 6 vs 6.
Example 2
- Input:
- packets = [4, 1, 5, 9, 13]
- Output:
- 5
Example 3
- Input:
- packets = [5]
- Output:
- 0
Constraints
- 1 ≤ packets.length ≤ 2 · 10^4
- 0 ≤ packets[i] < 2^31
Hint
Show the first hint
If two adjacent parts have equal XOR, what is the XOR of their union?
Walkthrough
How to approach it
01Clarify before coding
- Must both parts be non-empty? Yes: i < j guarantees the left part is non-empty and j ≤ k the right one.
- How big can the answer be? Up to about n³/6 ≈ 1.3 · 10^12 for n = 2 · 10^4, so use 64-bit integers (JavaScript numbers are exact up to 2^53).
02Brute force
Enumerate all (i, j, k) and compute both XORs, or fix (i, k), test whether the whole segment XORs to 0, and add k - i.
Cost: O(n³) for the first, O(n²) for the second: 4 · 10^8 pair checks at n = 2 · 10^4, still too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.