[SOLUTUON] Playing with OR Solution Codechef

Problem Solution Codechef

You are given an array $A$ containing $N$ integers, and an integer $K$ ($1\le K\le N$).
Find the number of subarrays of $A$ with length $K$ whose bitwise OR is odd.

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

Input Format

• The first line of input will contain a single integer $T$, 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 $N$ and $K$ — the length of the array and the subarray size you have to check, respectively.
  • The second line of each test contains $N$ space-separated integers �1,�2,…,��A1​,A2​,…,AN​ — the elements of the array.

Output Format

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

Constraints

Sample 1:

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 $K=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):
# 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[0]

# 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)