Split Into Equal-XOR Halves

Medium

You are given an array values of positive integers. Pick three indices i < j ≤ k and cut the segment values[i..k] before position j into two non-empty parts: - left: values[i] ^ ... ^ values[j - 1] - right: values[j] ^ ... ^ values[k] Here ^ is bitwise exclusive OR (XOR). Return the number of triples (i, j, k) for which the XOR of the left part equals the XOR of the right part.

Example 1

values=[4, 4] → 1

The only triple is (0, 1, 1): [4] on the left, [4] on the right, both with XOR 4.

Example 2

values=[1, 2, 3] → 2

1 ^ 2 ^ 3 = 0, so any cut of the segment [0, 2] works: (0, 1, 2) and (0, 2, 2). The answer is 2.

Example 3

values=[6, 9, 15, 6, 6] → 9

Constraints

1 ≤ len(values) ≤ 300
1 ≤ values[i] ≤ 10⁸

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Hash Table Math Prefix Sum

Similar problems

A Stretch Divisible by k Medium Eight Lamps After Many Nights Medium Palindrome After a Few Fixes Medium Stretches With k Odd Numbers Medium Fewest Lines Through the Dots Medium

Input

values=[4, 4]

Expected

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