# PROBLEM LINK:

**Author:** Rohit Tawde

**Tester:** Gaurish Baliga

**Editorialist:** Rohit Tawde

# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

Math.

# PROBLEM:

Can there be a binary string of size N, containing M number of 1's such that every substring of size K has an odd number of 1's?

# EXPLANATION:

**Claim**: \forall_{i = 1}^{N-K} a_i = a_{i+k}.

**Proof**: For every pair of consecutive of consecutive substrings of size k (first one starting from a_i), the elements form a_{i+1} to a_{i+k-1} are common. Therefore, the XOR of both the substrings can only be same when a_i = a_{i+k}.

Following this pattern, the whole string can be partitioned into \lfloor \frac{N}{K} \rfloor identical substrings of size K and 1 substring of size N\%K.

Let there be X number of 1's in the first partition (of size \lfloor \frac{N}{K} \rfloor) and Y number of 1's in the last partition (of size N\%K).

We get, M = (X*\lfloor \frac{N}{K} \rfloor) +Y.

\therefore Y = (X*\lfloor \frac{N}{K} \rfloor) - M.

We know that, 0 \leq Y \leq (N\%K). Also, even this partial partition will follow the same repeating pattern.

Therefore, we will get Y_{min} when we fill the first partition such that all the 0's are present before all the 1's.

\therefore Y_{min} = max[0,\space K - N + (N\%K)]

Similarly, to get Y_{max} we will keep all the 1's before all the 0's.

\therefore Y_{max} = min[X,\space (N\%K)]

Now we have to just find if there exists an odd X such that 1 \leq X \leq K and Y_{min} \leq M-(X*\lfloor \frac{N}{K} \rfloor) \leq Y_{max}.

# TIME COMPLEXITY:

O(K) per test case.

## SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
using namespace std;
int main() {
fast_io;
int t;
cin>>t;
while(t--){
ll n,m,k;
cin>>n>>m>>k;
ll ans=0;
ll f=0;
for(int i =1;i<=k;i+=2){
ll tm=n/k;
if(m>=tm*i+max(0ll, i-k+n%k) && m<=tm*i+min(n%k, (ll)i))f=1;
}
if(f){
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
return 0;
}
```