Given an array of integers arr.
We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).
Let's define a and b as follows:

a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note that ^ denotes the bitwise-xor operation.
Return the number of triplets (i, j and k) Where a == b.
 
Example 1:
Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)

Example 2:
Input: arr = [1,1,1,1,1]
Output: 10

Example 3:
Input: arr = [2,3]
Output: 0

Example 4:
Input: arr = [1,3,5,7,9]
Output: 3

Example 5:
Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8

 
Constraints:

1 <= arr.length <= 300
1 <= arr[i] <= 10^8

Source: leetcode | Difficulty: MEDIUM
Tags: Mathematics

Bit manipulation

Data structures

Range queries

Starter code: class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        

Solutions:
class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		res = xors = 0
		freq = collections.defaultdict(int, {0: 1})
		_sum = collections.defaultdict(int)
		for i in range(n):
			xors ^= arr[i]
			res += freq[xors] * i - _sum[xors]
			freq[xors] += 1
			_sum[xors] += i + 1
		return res


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		store = [0]
		n = len(arr)
		for i in range(n):
			store.append(arr[i] ^ store[i])
		ans = 0
		print(store)
		for i in range(1, n):
			for k in range(i + 1, n + 1):
				if store[i - 1] == store[k]:
					ans += k - i
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		ans = 0
		for i in range(n):
			p1 = [0] * (n + 1)
			p1[i] = arr[i]
			for j in range(i + 1, n):
				p1[j] = p1[j - 1] ^ arr[j]
				p2 = [0] * (n + 1)
				for k in range(j, n):
					p2[k] = p2[k - 1] ^ arr[k]
					if p1[j - 1] == p2[k]:
						ans += 1
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		arr = [0] + arr
		res = 0
		for k in range(1, len(arr)):
			arr[k] ^= arr[k - 1]
			for j in range(1, k + 1):
				for i in range(1, j):
					b = arr[k] ^ arr[j - 1]
					a = arr[j - 1] ^ arr[i - 1]
					if a == b:
						res += 1
		return res


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		ans = 0
		pool = dict()
		pool[0, 0] = 0
		pool[1, 1] = 0
		for i in range(len(arr) - 1):
			for j in range(i + 1, len(arr)):
				if (i, j) not in pool:
					a = pool[i, j - 1] ^ arr[j - 1]
					pool[i, j] = a
				else:
					a = pool[i, j]
				for k in range(j, len(arr)):
					if (j, k + 1) not in pool:
						if j == k:
							b = arr[k]
						else:
							b = pool[j, k] ^ arr[k]
						pool[j, k + 1] = b
					else:
						b = pool[j, k + 1]
					if a == b:
						ans += 1
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		prefix = [0] * n
		prefix[0] = arr[0]
		for i in range(1, n):
			prefix[i] = prefix[i - 1] ^ arr[i]
		ans = 0
		for i in range(n - 1):
			for j in range(i + 1, n):
				for k in range(j, n):
					t = prefix[i - 1] if i > 0 else 0
					if prefix[j - 1] ^ t == prefix[k] ^ prefix[j - 1]:
						ans += 1
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		xor = arr.copy()
		for i in range(1, len(xor)):
			xor[i] ^= xor[i - 1]
		print([bin(z) for z in arr])
		print([bin(z) for z in xor])
		count = 0
		for i in range(len(arr) - 1):
			for j in range(i + 1, len(arr)):
				for k in range(j, len(arr)):
					a = xor[j - 1] if i == 0 else xor[j - 1] ^ xor[i - 1]
					b = xor[k] ^ xor[j - 1]
					if a == b:
						count += 1
		return count


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		res = 0
		n = len(arr)
		for i in range(n - 1):
			tmp = arr[i]
			for j in range(i + 1, n):
				tmp = tmp ^ arr[j]
				if tmp == 0:
					res += j - i
		return res


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		(ans, size) = (0, len(arr))
		xor = [0] * size
		xor[0] = arr[0]
		for i in range(1, size):
			xor[i] = arr[i] ^ xor[i - 1]
		for i in range(size):
			for j in range(i + 1, size):
				for k in range(j, size):
					a = xor[j - 1] ^ xor[i - 1] if i > 0 else xor[j - 1]
					b = xor[k] ^ xor[j - 1]
					if a == b:
						ans += 1
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		a = []
		n = len(arr)
		for i in range(n):
			if i == 0:
				a.append(arr[i])
			else:
				a.append(arr[i] ^ a[-1])
		ans = 0
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j, n):
					x = a[j - 1] ^ (0 if i == 0 else a[i - 1])
					y = a[k] ^ a[j - 1]
					if x == y:
						ans += 1
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		prefix = [arr[0]]
		for i in range(1, len(arr)):
			prefix.append(prefix[-1] ^ arr[i])
		ans = 0
		for i in range(1, len(prefix)):
			for j in range(i + 1, len(prefix)):
				if prefix[i - 1] ^ prefix[j] == 0:
					ans += j - i
		for i in range(len(prefix)):
			if prefix[i] == 0:
				ans += i
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		N = len(arr)
		(A, pre) = ([arr[0]], arr[0])
		for ii in arr[1:]:
			pre ^= ii
			A.append(pre)
		res = 0
		for ii in range(N):
			for kk in range(ii + 1, N):
				(a_i, a_k) = (A[ii - 1] if ii else 0, A[kk])
				a_ik = a_k ^ a_i
				if not a_ik:
					res += kk - ii
		return res


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		xors = [arr[0]]
		for i in range(1, len(arr)):
			xors.append(xors[-1] ^ arr[i])
		print(xors)
		n = len(arr)
		count = 0
		for i in range(n - 1):
			for j in range(i + 1, n):
				temp = xors[j]
				if i > 0:
					temp ^= xors[i - 1]
				if temp == 0:
					count += j - i
		return count


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		prefix = [0] * (len(arr) + 1)
		prefix[1] = arr[0]
		res = 0
		for i in range(1, len(arr)):
			prefix[i + 1] = prefix[i] ^ arr[i]
		print(prefix)
		for i in range(len(arr) - 1):
			for j in range(i, len(arr)):
				if prefix[j + 1] ^ prefix[i] == 0:
					res += j - i
		return res


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		preXor = [0] * (len(arr) + 1)
		preXor[0] = arr[0]
		for i in range(1, len(arr)):
			preXor[i] = preXor[i - 1] ^ arr[i]
		ret = 0
		for i in range(len(arr) - 1):
			l = preXor[i - 1]
			for k in range(i + 1, len(arr)):
				if l == preXor[k]:
					ret += k - i
		return ret


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		(count, n) = (0, len(arr))
		for i in range(n - 1):
			accu = arr[i]
			for k in range(i + 1, n):
				accu ^= arr[k]
				if accu == 0:
					count += k - i
		return count


class Solution:

	def allPrefixXor(self, arr: List[int]) -> List[int]:
		prefix_xor: List[int] = [0] * len(arr)
		prefix_xor[0] = arr[0]
		for i in range(1, len(arr)):
			prefix_xor[i] = prefix_xor[i - 1] ^ arr[i]
		return prefix_xor

	def allSegmentXor(self, arr: List[int]) -> List[List[int]]:
		prefix_xor: List[int] = self.allPrefixXor(arr)
		segment_xor: List[List[int]] = [[0] * len(arr) for _ in range(len(arr))]
		segment_xor[0] = prefix_xor[:]
		for first in range(1, len(segment_xor) - 1):
			for last in range(first + 1, len(segment_xor[first])):
				segment_xor[first][last] = prefix_xor[last] ^ prefix_xor[first - 1]
		return segment_xor

	def countTriplets(self, arr: List[int]) -> int:
		segment_xor: List[List[int]] = self.allSegmentXor(arr)
		n_triplets: int = 0
		for first in range(len(segment_xor) - 1):
			for last in range(first + 1, len(segment_xor[first])):
				if segment_xor[first][last] == 0:
					n_triplets += last - first
		return n_triplets


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		d = defaultdict(set)
		s = 0
		d[0].add(-1)
		for (i, x) in enumerate(arr):
			s ^= x
			d[s].add(i)
		return sum([abs(a - b) - 1 for k in d for (a, b) in combinations(d[k], 2)])


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		triplets = 0
		for (i, a) in enumerate(arr):
			subrange = []
			for (j, b) in enumerate(arr[i:]):
				j_absolute = i + j
				if j_absolute == i:
					subrange.append(b)
				else:
					subrange.append(subrange[-1] ^ b)
				if subrange[-1] == 0:
					triplets += j
		return triplets


import numpy as np

class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		cumxor = [arr[0]]
		for k in range(1, len(arr)):
			cumxor.append(cumxor[-1] ^ arr[k])
		counter = 0
		for x in range(1, len(arr)):
			if cumxor[x] == 0:
				counter += x
			for y in range(x):
				if cumxor[x] == cumxor[y]:
					counter += x - y - 1
		return counter


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		memo = [arr[:] for _ in range(len(arr))]
		for i in range(len(arr)):
			tmp = arr[i]
			for j in range(i + 1, len(arr)):
				tmp ^= arr[j]
				memo[i][j] = tmp
		return sum([(j - i) * (memo[i][j] == 0) for i in range(len(arr)) for j in range(i + 1, len(arr))])


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		res = 0
		dp = [[0 for i in range(len(arr))] for j in range(len(arr))]
		for i in range(len(arr)):
			for j in range(i, len(arr)):
				a = 0
				if j == i:
					a = arr[i]
				else:
					a = dp[i][j - 1] ^ arr[j]
				dp[i][j] = a
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				if dp[i][j] == 0:
					res += j - i
		return res


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		if len(arr) < 2:
			return 0
		xors = [i for i in arr]
		for i in range(1, len(xors)):
			xors[i] ^= xors[i - 1]
		ans = 0
		for j in range(1, len(xors)):
			cnt = Counter([xors[j - 1] ^ xors[i - 1] for i in range(1, j)])
			cnt[xors[j - 1]] = cnt.get(xors[j - 1], 0) + 1
			for k in range(j, len(xors)):
				ans += cnt.get(xors[k] ^ xors[j - 1], 0)
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		count = 0
		for j in range(1, n):
			right_xor = collections.defaultdict(int)
			curr_xor = 0
			for k in range(j, n):
				curr_xor ^= arr[k]
				right_xor[curr_xor] += 1
			curr_xor = 0
			for i in range(j - 1, -1, -1):
				curr_xor ^= arr[i]
				if curr_xor in right_xor:
					count += right_xor[curr_xor]
		return count


class Solution:

	def countTriplets(self, arr: List[int]) -> int:

		@lru_cache(None)
		def xor_reduce(i, j):
			if j - i == 1:
				return arr[i] ^ arr[j]
			else:
				return xor_reduce(i + 1, j) ^ arr[i]
		ans = 0
		N = len(arr)
		for i in range(N):
			for j in range(i + 1, N):
				x = xor_reduce(i, j)
				if x == 0:
					ans += j - i
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		from collections import defaultdict as dd
		n = len(arr)
		cnt = 0
		dp = [[-1] * n for i in range(n)]
		for i in range(n):
			curr = arr[i]
			dp[i][i] = curr
			for j in range(i + 1, n):
				curr = curr ^ arr[j]
				dp[i][j] = curr
		for i in range(1, n):
			map = dd(int)
			for j in range(i):
				map[dp[j][i - 1]] += 1
			for j in range(i, n):
				cnt += map[dp[i][j]]
				if map[dp[i][j]] == 0:
					del map[dp[i][j]]
		return cnt


from collections import defaultdict as dd

class Solution:

	def countTriplets(self, a):
		n = len(a)
		cnt = 0
		dp = [[-float('inf')] * n for i in range(n)]
		for i in range(n):
			curr = a[i]
			dp[i][i] = curr
			for j in range(i + 1, n):
				curr = curr ^ a[j]
				dp[i][j] = curr
		for i in range(1, n):
			map = dd(int)
			for j in range(i):
				map[dp[j][i - 1]] += 1
			for j in range(i, n):
				cnt += map[dp[i][j]]
				if map[dp[i][j]] == 0:
					del map[dp[i][j]]
		return cnt


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		d = defaultdict(list)
		d[0].append(-1)
		(cur, rst) = (0, 0)
		for (i, a) in enumerate(arr):
			cur ^= a
			if i > 0:
				for j in d[cur]:
					rst += i - j - 1
			d[cur].append(i)
		return rst


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		ans = 0
		for i in range(1, n):
			l = Counter()
			a = 0
			for j in range(i - 1, -1, -1):
				a ^= arr[j]
				l[a] += 1
			a = 0
			for j in range(i, n):
				a ^= arr[j]
				ans += l[a]
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		d = {}
		xormat = [[0] * (n + 1) for i in range(n)]
		for i in range(n):
			for j in range(i + 1, n + 1):
				xormat[i][j] = v = xormat[i][j - 1] ^ arr[j - 1]
				if v in d:
					d[v].append((i, j))
				else:
					d[v] = [(i, j)]
		count = 0
		from collections import defaultdict
		for values in list(d.values()):
			counts = defaultdict(list)
			for (i, j) in values:
				counts[i].append(j)
			for v in values:
				count += len(counts[v[1]])
		return count


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		values = {}
		for i in range(len(arr)):
			val = 0
			for j in range(i, len(arr)):
				val ^= arr[j]
				if val not in values:
					values[val] = {'start': {}, 'end': {}}
				if i not in values[val]['start']:
					values[val]['start'][i] = 0
				values[val]['start'][i] += 1
				if j not in values[val]['end']:
					values[val]['end'][j] = 0
				values[val]['end'][j] += 1
		total = 0
		for val in values:
			for index in values[val]['end']:
				if index + 1 in values[val]['start']:
					total += values[val]['start'][index + 1] * values[val]['end'][index]
		return total


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		(ans, n) = (0, len(arr))
		xors = [0] * (n + 1)
		for i in range(1, n + 1):
			xors[i] = xors[i - 1] ^ arr[i - 1]
		for i in range(n):
			for k in range(i + 1, n):
				if xors[k + 1] ^ xors[i] != 0:
					continue
				for j in range(i + 1, k + 1):
					if xors[j] ^ xors[i] == xors[k + 1] ^ xors[j]:
						ans += 1
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		prefixes = [arr[0]]
		result = 0
		for i in range(1, n):
			prefixes.append(arr[i] ^ prefixes[-1])
		for i in range(n - 1):
			for k in range(i + 1, n):
				sub_array_xor = prefixes[k] if i == 0 else prefixes[k] ^ prefixes[i - 1]
				if sub_array_xor == 0:
					for j in range(i + 1, k + 1):
						left_part = prefixes[j - 1] if i == 0 else prefixes[j - 1] ^ prefixes[i - 1]
						right_part = prefixes[k] ^ prefixes[j - 1]
						if left_part == right_part:
							result += 1
		return result


class Solution:

	def countTriplets(self, arr: List[int]) -> int:

		def xor(arr):
			xor = 0
			for a in arr:
				xor ^= a
			return xor
		result = 0
		for i in range(0, len(arr)):
			for j in range(i + 1, len(arr)):
				if xor(arr[i:j + 1]) == 0:
					result += j - i
		return result


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		N = len(arr)
		ans = 0
		for i in range(N - 1):
			v = arr[i]
			l = [v]
			for k in range(i + 1, N):
				v ^= arr[k]
				for w in l:
					if v ^ w == w:
						ans += 1
				l.append(v)
		return ans


class Solution:

	def countTriplets(self, A: List[int]) -> int:
		res = cur = 0
		count = {0: [1, 0]}
		for (i, a) in enumerate(A):
			cur ^= a
			(n, total) = count.get(cur, [0, 0])
			res += i * n - total
			count[cur] = [n + 1, total + i + 1]
		return res


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		ans = 0
		print(len(arr[:-1]))
		for key1 in range(len(arr[:-1])):
			a = 0
			for (key2, j) in enumerate(arr[key1:]):
				a ^= j
				b = 0
				for k in arr[key2 + key1 + 1:]:
					b ^= k
					if b == a:
						ans += 1
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		if n < 2:
			return 0
		out = 0
		for i in range(n - 1):
			a = arr[i]
			for j in range(i + 1, n):
				b = 0
				for k in range(j, n):
					b ^= arr[k]
					if a == b:
						out += 1
				a ^= arr[j]
		return out


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		count = 0
		n = len(arr)
		for i in range(n - 1):
			x = arr[i]
			for j in range(i + 1, n):
				y = 0
				for k in range(j, n):
					y = y ^ arr[k]
					if x == y:
						count += 1
				x = x ^ arr[j]
		return count


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		l = len(arr)
		if l == 1:
			return 0
		mat = [[0 for i in range(l)] for i in range(l)]
		for i in range(l - 1):
			mat[i][i + 1] = arr[i] ^ arr[i + 1]
			for j in range(i + 2, l):
				mat[i][j] = mat[i][j - 1] ^ arr[j]
		count = 0
		for i in range(l - 1):
			for j in range(i + 1, l):
				curr = mat[i][j - 1]
				if i + 1 == j:
					curr = arr[i]
				for k in range(j, l):
					pres = mat[j][k]
					if j == k:
						pres = arr[j]
					if curr == pres:
						count += 1
		return count


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		res = 0
		for i in range(len(arr) - 1):
			accu = arr[i]
			for k in range(i + 1, len(arr)):
				accu ^= arr[k]
				if not accu:
					res += k - i
		return res


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		prefix_xor = [arr[0]]
		answer = 0
		for i in range(1, len(arr)):
			prefix_xor.append(prefix_xor[i - 1] ^ arr[i])
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				a = prefix_xor[j]
				if i > 0:
					a = a ^ prefix_xor[i - 1]
				for k in range(j, len(arr)):
					b = prefix_xor[k] ^ prefix_xor[j]
					if a == b:
						answer += 1
		return answer


class Solution:

	def countTriplets(self, a: List[int]) -> int:
		p = [a[0]]
		for i in range(1, len(a)):
			p.append(p[-1] ^ a[i])
		ans = 0
		for i in range(len(a) - 1):
			for j in range(i + 1, len(a)):
				v = p[j] ^ p[i] ^ a[i]
				for k in range(j, len(a)):
					vv = p[k] ^ p[j]
					if v == vv:
						ans += 1
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		res = 0
		xors = [0] * (n + 1)
		for z in range(n):
			xors[z] = xors[z - 1] ^ arr[z]
		for i in range(n - 1):
			for j in range(i + 1, n):
				for k in range(j, n):
					if xors[i - 1] ^ xors[k] == 0:
						res += 1
		return res


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		xor = [[0] * len(arr) for _ in range(len(arr))]
		for i in range(len(arr)):
			for j in range(i, len(arr)):
				if j == i:
					xor[i][j] = arr[j]
				else:
					xor[i][j] = xor[i][j - 1] ^ arr[j]
		ans = 0
		for i in range(len(arr) - 1):
			for j in range(i + 1, len(arr)):
				for k in range(j, len(arr)):
					if xor[i][j - 1] == xor[j][k]:
						ans += 1
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		start = arr[0]
		res = 0
		for i in range(1, len(arr)):
			start ^= arr[i]
			arr[i] = start
		arr = [0] + arr
		for i in range(1, len(arr)):
			for j in range(i + 1, len(arr)):
				first_part = arr[j - 1] ^ arr[i - 1]
				for k in range(j, len(arr)):
					second_part = arr[k] ^ arr[j - 1]
					if first_part == second_part:
						res += 1
		return res


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		count = 0
		for i in range(1, len(arr)):
			arr[i] ^= arr[i - 1]
		for i in range(0, len(arr) - 1):
			for j in range(i + 1, len(arr)):
				target = arr[j - 1]
				if i > 0:
					target ^= arr[i - 1]
				for k in range(j, len(arr)):
					curr = arr[k]
					curr ^= arr[j - 1]
					if curr == target:
						count += 1
		return count


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		dp = [[0] * n for i in range(n)]
		for i in range(n):
			dp[i][i] = arr[i]
		for i in range(n - 1, -1, -1):
			for j in range(i + 1, n):
				dp[i][j] = dp[i][j - 1] ^ arr[j]
		output = 0
		for i in range(n - 1, -1, -1):
			for j in range(i + 1, n):
				for k in range(i + 1, j + 1):
					if dp[i][k - 1] == dp[k][j]:
						output += 1
		return output


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		s = [0] * (len(arr) + 1)
		for i in range(1, len(arr) + 1):
			s[i] = s[i - 1] ^ arr[i - 1]
		ans = 0
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				for k in range(j, len(arr)):
					if s[k + 1] ^ s[j] == s[j] ^ s[i]:
						ans += 1
		return ans


from collections import defaultdict

class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		x = [0]
		for t in arr:
			x.append(x[-1] ^ t)
		ans = 0
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j, n):
					if x[j] ^ x[i] == x[k + 1] ^ x[j]:
						ans += 1
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		cum = [0]
		for n in arr:
			cum.append(cum[-1] ^ n)
		ans = 0
		for i in range(0, len(arr) - 1):
			for k in range(i + 1, len(arr)):
				for j in range(i + 1, k + 1):
					if cum[i] ^ cum[j] == cum[k + 1] ^ cum[j]:
						ans += 1
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		c = 0
		xor = 0
		for i in range(n - 1):
			xor = arr[i]
			for j in range(i + 1, n):
				xor ^= arr[j]
				if xor == 0:
					c += j - i
		return c


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		preXor = [0] * (len(arr) + 1)
		for (i, element) in enumerate(arr):
			preXor[i + 1] = preXor[i] ^ element
		count = 0
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				for k in range(j, len(arr)):
					a = preXor[j] ^ preXor[i]
					b = preXor[k + 1] ^ preXor[j]
					if a == b:
						count += 1
		return count


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		prefixSum = [0] * (len(arr) + 1)
		for (i, v) in enumerate(arr):
			prefixSum[i + 1] = prefixSum[i] ^ v
		ans = 0
		for i in range(1, len(prefixSum)):
			for j in range(i + 1, len(prefixSum)):
				for k in range(j, len(prefixSum)):
					if prefixSum[i - 1] ^ prefixSum[j - 1] == prefixSum[j - 1] ^ prefixSum[k]:
						ans += 1
		return ans


class Solution:

	def countTriplets(self, arr: List[int]) -> int:

		def get_triplets(nums):
			n = len(nums)
			triplets = 0
			i = 0
			while i < n - 1:
				lsum = nums[i]
				j = i + 1
				while j < n:
					k = j
					rsum = nums[j]
					while k < n:
						if lsum == rsum:
							triplets += 1
						k += 1
						if k < n:
							rsum = rsum ^ nums[k]
					j += 1
					lsum = lsum ^ nums[j - 1]
				i += 1
			return triplets
		return get_triplets(arr)


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		n = len(arr)
		xorarr = [arr[0]]
		for i in range(1, n):
			xorarr.append(xorarr[-1] ^ arr[i])
		count = 0
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j, n):
					if xorarr[k] ^ xorarr[j - 1] == xorarr[j - 1] ^ (xorarr[i - 1] if i > 0 else 0):
						count += 1
		return count


from itertools import accumulate

class Solution:

	def countTriplets(self, nums: List[int]) -> int:
		(n, x) = (len(nums), list(accumulate(nums, lambda x, y: x ^ y, initial=0)))
		count = 0
		for i in range(1, n + 1 - 1):
			for j in range(i + 1, n + 1):
				for k in range(j + 0, n + 1):
					if x[i - 1] ^ x[j - 1] == x[j - 1] ^ x[k]:
						count += 1
		return count


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		prexor = [0]
		for num in arr:
			prexor.append(prexor[-1] ^ num)
		cnt = 0
		for i in range(1, len(arr) + 1):
			for j in range(i + 1, len(arr) + 1):
				for k in range(i + 1, j + 1):
					if prexor[k - 1] ^ prexor[i - 1] == prexor[j] ^ prexor[k - 1]:
						cnt += 1
		return cnt


class Solution:

	def countTriplets(self, arr: List[int]) -> int:
		if not arr:
			return 0
		x = [0, arr[0]]
		for i in range(1, len(arr)):
			x.append(x[-1] ^ arr[i])
		cnt = 0
		for i in range(1, len(x)):
			for j in range(i + 1, len(x)):
				for k in range(j, len(x)):
					if x[j - 1] ^ x[i - 1] == x[k] ^ x[j - 1]:
						cnt += 1
		return cnt