Loading...
Loading...
Loading...
A college Wi-Fi router logs one numeric code per minute for n minutes. To check a stretch of minutes, the network team combines all its codes with XOR (the ^ operator in Java), one after another.
Count the stretches of one or more consecutive minutes whose combined XOR is exactly k.
Example 1
Input
5 6 4 2 2 6 4
Output
4
Four stretches work: 4 2, 4 2 2 6, 2 2 6 and 6.
Example 2
Input
3 7 1 1 1
Output
0
Every stretch gives 1 or 0, never 7.
Try the problem first. Open one hint at a time.
XOR has a useful rule: if a ^ b = c, then a ^ c = b. And x ^ x = 0.
Let run be the XOR of minutes 1 to j. A stretch ending at j has XOR k when an earlier running XOR equals run ^ k.
Count running XOR values in a HashMap, starting with 0 seen once for "before minute 1".
The count can reach about 5 × 10^9 when n = 10^5, so keep it in a long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor