Range XOR Lookups

Medium

A sensor logs positive numbers values. To verify pieces of the log, you need a fast checksum of any range: the bitwise XOR of its elements. You get a list of queries ranges, where ranges[i] = [l, r]. For each query, compute values[l] XOR values[l + 1] XOR ... XOR values[r] (both ends included). Return the answers in the order of the queries.

Example 1

values=[6, 3, 5, 9], ranges=[[0, 1], [1, 3], [2, 2], [0, 3]] → [5, 15, 5, 9]

6 XOR 3 = 5; 3 XOR 5 XOR 9 = 15; a one-element range is just that element, 5; the whole array gives 6 XOR 3 XOR 5 XOR 9 = 9.

Example 2

values=[7, 7, 7], ranges=[[0, 1], [0, 2]] → [0, 7]

Two equal numbers cancel out, so the first answer is 0 and the second is 7.

Constraints

1 ≤ len(values), len(ranges) ≤ 3·10⁴
1 ≤ values[i] ≤ 10⁹
ranges[i] = [l, r], 0 ≤ l ≤ r < len(values)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Prefix Sum

Similar problems

Palindrome After a Few Fixes Medium Split Into Equal-XOR Halves Medium K-th Largest Corner XOR Medium XOR Top-Up While Trimming Medium Products of Binary Pieces Medium

Input

values=[6, 3, 5, 9], ranges=[[0, 1], [1, 3], [2, 2], [0, 3]]

Expected

[5, 15, 5, 9]

Run checks the first 3 tests in your browser. Submit checks all 76 tests on the server, hidden ones included.