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 �.
- 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.
For each test case, output on a new line the number of length-� subarrays of � whose bitwise OR is odd.
- The sum of � across all tests doesn’t exceed 5⋅105.
2 5 2 5 7 13 4 6 4 3 2 6 7 4
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.
# Number of test cases
T = int(input())
# Iterate through each test case
for _ in range(T):
# Read N and K
N, K = map(int, input().split())
# Read the array A
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