SUBXOR - SubXor

no tags 

A straightforward question. Given an array of positive integers you have to print the number of subarrays whose XOR is less than K. Subarrays are defined as a sequence of continuous elements Ai, Ai+1, ..., Aj . XOR of a subarray is defined as Ai ^ Ai+1 ^ ... ^ Aj. Symbol ^ is Exclusive Or. You can read more about it here:
http://en.wikipedia.org/wiki/Exclusive_or

Input Format:

First line contains T, the number of test cases. Each of the test case consists of N and K in one line, followed by N space separated integers in next line.

Output Format:

For each test case, print the required answer.

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^5
1 ≤ K ≤ 10^6
Sum of N over all testcases will not exceed 10^5.

Sample Input:

1
5 2
4 1 3 2 7	

Sample Output:

3

Explanation:

Only subarrays satisfying the conditions are [1], [1,3,2] and [3,2].


Problem Setter: Lalit Kundu


hide comments
aqua4: 2018-08-18 12:50:25

Nice problem!

Last edit: 2018-08-18 12:56:17
ap_222: 2018-06-16 05:49:13

In Case if anyone needs help.

https://ide.geeksforgeeks.org/jdClUUNh7A

sanyam123: 2018-01-28 16:09:18

I think there is some bug with time limits firstly same problem on codechef is getting AC(1.83 sec) with time limit of 2 seconds . Here solution with 1.54s is getting AC so what's the point of stating time limit of 1 sec. @ darkshadows

ibrahim5253: 2017-11-10 20:18:29

Don't forget nothing.

Shubham Sinha: 2016-06-25 10:37:17

make the number of bits in all the numbers that u will be processing equal which can be done by adding leading zeros for example make the number of bits in all numbers equal to 20 and then proceed, this will avoid any wrong answers.

akhil3sh: 2016-03-03 11:24:35

use long long for answer

Gaurav Arora: 2016-02-06 17:55:18

I had to use fast input using getchar_unlocked to avoid TLE
This kinda kills the spirit.

anando_du: 2015-05-26 17:56:25

time 1 s . I got ac 1.54 s :v :v
btw nice problem ^_^

Praneeth.N: 2015-03-15 08:37:05

@darkshadows : Can you please help me..I keep getting wrong answer after 18/19 test case.

[reply by cyclops: Judging does not halt on first failure.]

Last edit: 2015-03-15 16:24:57
:D: 2015-02-02 21:45:07

Only three subarrays listed in "Explanation" meet the problem criteria:
1 < 2
1^3^2 = 0 < 2
3^2 = 1 < 2


Added by:darkshadows
Date:2014-01-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64