# [SOLUTUON] Playing with OR Solution Codechef

## Problem Solution Codechef

You are given an array  containing  integers, and an integer  (1≤�≤�).
Find the number of subarrays of  with length  whose bitwise OR is odd.

Note: A subarray of  is a contiguous segment of elements of .
For example, if �=[1,3,2], then it has 6 non-empty subarrays: ,,,[1,3],[3,2],[1,3,2].
In particular, [1,2] is not a subarray of .

### Input Format

• The first line of input will contain a single integer , denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains two space-separated integers  and  — the length of the array and the subarray size you have to check, respectively.
• The second line of each test contains  space-separated integers �1,�2,…,�� — the elements of the array.

### Output Format

For each test case, output on a new line the number of length- subarrays of  whose bitwise OR is odd.

### Constraints

• 1≤�≤105
• 1≤�≤�≤5⋅105
• 1≤��≤109
• The sum of  across all tests doesn’t exceed 5⋅105.

### Sample 1:

Input

Output

2
5 2
5 7 13 4 6
4 3
2 6 7 4

3
2

### Explanation:

Test case 1: There are four subarrays of length �=2.

• [5,7], with bitwise OR equal to 7.
• [7,13], with bitwise OR equal to 15.
• [13,4], with bitwise OR equal to 13.
• [4,6], with bitwise OR equal to 6.

Three of them are odd, so the answer is 3.

Test case 2: There are two subarrays of length three, both of them have odd bitwise OR.

SOLUTION

# Number of test cases
T = int(input())

# Iterate through each test case
for _ in range(T):
N, K = map(int, input().split())

A = list(map(int, input().split()))

# Count of subarrays with odd bitwise OR
count_odd = 0

# Iterate through the array and check subarrays of length K
for i in range(N – K + 1):
subarray = A[i:i + K]
bitwise_or = subarray

# Calculate the bitwise OR of the subarray
for j in range(1, K):
bitwise_or |= subarray[j]

# Check if the bitwise OR is odd
if bitwise_or % 2 == 1:
count_odd += 1

# Output the count of subarrays with odd bitwise OR
print(count_odd)