PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Authors: naisheel, jalp1428
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
1365
PREREQUISITES:
None
PROBLEM:
Given an array A and a window size K, find the number of subarrays of A of length K whose bitwise OR is odd.
EXPLANATION:
First, we observe that an integer is odd if and only if it has the 0-th bit set.
It’s fairly easy to see why: the only odd power of 2 is 2^0 = 1, so if N can be written as the sum of several powers of 2 that don’t include 2^0, then N is the sum of several even numbers (and hence is itself even).
Bitwise OR is a bitwise operation, meaning it operates separately on each bit.
As noted above though, we only care about the 0-th bit - in particular, the bitwise OR of several integers is odd if and only if at least one of the numbers is odd.
This allows to restate our task as: find the number of subarrays of A of length K, such that they contain at least one odd number.
Of course, since N is large we don’t have the luxury of checking every possible subarray in \mathcal{O}(K) time each.
Solving this problem faster can be done in a variety of ways though.
One simple algorithm is to use a sliding window algorithm, as follows:
- First, count the number of odd integers in the first subarray, i.e, [A_1, A_2, \ldots ,A_K].
This is done with a simple loop. - Next, we move to the subarray [A_2, A_3, \ldots A_{K+1}]$.
Here, instead of recomputing the entire thing, notice that there are only two changes: A_{K+1} got added into the subarray, and A_1 got removed.
So, it’s enough to add 1 to the counter if A_{K+1} is odd, and subtract 1 from the counter is A_1 is odd. - Repeat this one-step move again to get the count for [A_3, A_4, \ldots, A_{K+2}], and so on.
This way, we are able to quickly check all the subarrays of length K in \mathcal{O}(N) time.
The answer is the number of times the odd-number counter was positive.
TIME COMPLEXITY
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
vector<int>arr(n);
for(auto &x:arr)cin>>x;
int cnt=0;
for(int i=0;i<k-1;i++)
{
cnt+=(arr[i]%2);
}
int i=k-1;
int ans=0;
while(i<n)
{
cnt+=(arr[i]%2);
ans+=(cnt>=1);
cnt-=(arr[i-k+1]%2);
i++;
}
cout<<ans<<endl;
}
// your code goes here
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
oddct = 0
for i in range(k-1): oddct += a[i]%2
for i in range(k-1, n):
oddct += a[i]%2
ans += oddct > 0
oddct -= a[i-k+1]%2
print(ans)