Ensure that you are logged in and have the required permissions to access the test.

Count Subarrays

4.9

9 votes
Bit Manipulation, Basic Programming, Bit manipulation, Algorithms, Observation, Basics of Bit Manipulation, Mathematics
Problem

You are given an array A of size N. Your task is to find the number of subarrays within the given array such that the Bitwise XOR of all elements in the subarray has an odd number of set bits (i.e., 1s).

The subarray of A is a contiguous part of the array A, i. e. the array Ai,Ai+1,....,Aj for some 1ijN.

Input format

  • The first line contains a single integer T, which denotes the number of test cases.
  • For each test case:
    • The first line contains N denoting the size of array A.
    • The second line contains N space-separated integers, denoting the elements of A.

Output format

For each test case, print the number of subarrays within the given array such that the Bitwise XOR of all elements in the subarray has an odd number of set bits (i.e., 1s) in a new line.

Constraints

1T1051N1061A[i]109  i[1,N]The sum of all values of N over all test cases doesn't exceed 106

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For test case 1:

  • N = 3
  • A = [1, 2, 4]

In the given array there are the following 4 subarrays with their XOR having odd number of set bits:

  • [1]
  • [2]
  • [4]
  • [1, 2, 4]

Thus, the answer is 4.

Editor Image

?