Special Subarray

★★★★★

4.4

16 votes

, Binary Search, Algorithms

Details

Submissions

Discussion

Editorial

Problem

You are given an array $A$ of length $N$ . A subarray is called special if the XOR and Sum of the subarray are the same. Find the number of special subarrays of $A$ .

Input Format

The first line contains an integer $T$ , which denotes the number of test cases.
The first line of each test case contains an integer $N$ , which denotes the length of array $A$ .
The second line of each test case contains $N$ space-separated integers, denoting elements of array $A$ .

Output Format

For each test case, print the number of special subarrays of $A$ .

Constraints

$1 \leq T \leq 10 \\ 1 \leq N \leq 10^5 \\ 1 \leq A_i \leq 10^9$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For test case $1$ :

Subarray $[2]$ , sum=2, XOR=2.
Subarray $[2, 1]$ , sum=3, XOR=3.
Subarray $[2, 1, 6]$ , sum=9, XOR=5.
Subarray $[1]$ , sum=1, XOR=1.
Subarray $[1, 6]$ , sum=7, XOR=7.
Subarray $[6]$ , sum=6, XOR=6.

Hence, the answer is $5$ .

For test case $2$ :

Subarray $[4]$ , sum=4, XOR=4.
Subarray $[4, 5]$ , sum=9, XOR=1.
Subarray $[5]$ , sum=5, XOR=5.

Hence, the answer is $2$ .