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:


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.


For each test case, print the required answer.


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:

5 2
4 1 3 2 7	

Sample Output:



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

Problem Setter: Lalit Kundu

hide comments
ng_1997: 2022-04-17 21:54:23

for those who are getting WA, check for the arrays where all the elements are same.

lovro_nidogon1: 2020-08-24 14:19:57

A skudiba, skidibapiba

awesomeamul: 2020-03-23 14:40:34

please use long long for answer

shubham97361: 2019-07-30 23:15:36

tough to implement.

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

Nice problem!

Last edit: 2018-08-18 12:56:17
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.

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