# KLXOR - Editorial

Again XOR Problem :

Practice

Code Drive Contest Division 1

Code Drive Contest Division 2

Code Drive Contest Division 3

Author: Sobhagya Singh Dewal

Tester: Lavish Gupta , Takuki Kurokawa

EASY

# PREREQUISITES:

Strings ,Math, Prefix-arrays

# PROBLEM:

You may have solved a lot of problems related to XOR and we are sure that you liked them, so here is one more gift for you.
You are given a binary string S of length N, you need to find how many bits will be set in the XOR of all substrings of size K in the given string.

Note :

Number of set bits is the number of ones in a binary string.

A substring is a continuous part of string which can be obtained by deleting some(may be none) characterâs from front and some(may be none) characterâs from the end.

XOR of 2 binary string is the standard logical XOR.

# QUICK EXPLANATION:

There will be K index in the final string, and for each position we know which index will come from the initial string so we can just count the number of ones at each position.

# EXPLANATION:

In the question length of the string is N and we need to check for all K length substrings so we know that there will be total N-K+1 substrings of length K and we need to XOR all of them.

Lets say string S=S_{0}+S_{1}+S_{2}.....+S_{N-1} where S_{0},S_{1},S_{2}.....,S_{N-1} are N characters of strings.

And all K length substrings will be:

Sub_{0}=S_{0}+S_{1}+S_{2}+......+S_{K-1}

Sub_{1}=S_{1}+S_{2}+S_{3}+......+S_{K}

Sub_{2}=S_{2}+S_{3}+S_{4}+......+S_{K+1}

......

Sub_{N-K}=S_{N-K}+S_{N-K+1}+S_{N-K+2}+......+S_{N-1}

Now we know that in the final string at i^{th} position which characters will be occurs, so lets say final string is F then:

F_{0}=S_{0}\oplus S_{1}\oplus S_{2}.......\oplus S_{N-K}

F_{1}=S_{1}\oplus S_{2}\oplus S_{3}.......\oplus S_{N-K+1}

F_{2}=S_{2}\oplus S_{3}\oplus S_{4}.......\oplus S_{N-K+2}

........

F_{K-1}=S_{K-1}\oplus S_{K}\oplus S_{K+1}.......\oplus S_{N-1}

Now F_{i} can be easily calculated by number of ones from S_{i} to S_{N-K+i} that can be done with prefix array, we will store number of ones till i^{th} position in an array and then we can find number of ones in an range.

For example Pre_{i} is number of ones till i^{th} position in string S and we want to count number of ones from S_{i} to S_{N-K+i}

then it will be number of ones till S_{N-K+i}-number of ones till S_{i-1}.

So finally F_{i} will be (Pre_{N-K+i}-Pre_{i-1})\% 2.
Time Complexity: O(N) for each testcase.

# SOLUTIONS:

Setterâs Solution
``````#include <bits/stdc++.h>
using namespace std;

void myfun()
{
int n,k;
cin>>n>>k;
string s; cin>>s;
int pre[n+1];
pre[0]=0;
for(int i=0;i<n;i++)
{
pre[i+1]=pre[i];
if(s[i]=='1') pre[i+1]++;
}
int j=n-k+1,i=0;
int res=0;
while(j<=n)
{
int cur=pre[j]-pre[i];
res=res+(cur%2);
i++;
j++;
}
cout<<res<<"\n";
}

int main()
{
int t=1;
cin>>t;
while(t--)
myfun();
return 0;
}
``````
Tester's (Lavish Gupta) Solution
``````#include <bits/stdc++.h>
using namespace std;
#define ll long long

/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 10;
const int MAX_N = 200000;
const int MAX_SUM_N = 100000;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll z = 1000000007;
ll sum_nk = 0 ;

void solve()
{
int n = readIntSp(1 , MAX_N) ;
int k = readIntLn(1 , n) ;

sum_nk += (1LL * n * k) ;
max_n = max(n , max_n) ;
sum_n += n ;

string str = readStringLn(n , n) ;
for(int i = 0 ; i < n ; i++)
{
assert(str[i] == '0' || str[i] == '1') ;
}

int cnt[n] ;
cnt[0] = (str[0] == '1') ;

for(int i = 1 ; i < n ; i++)
{
cnt[i] = cnt[i-1] + (str[i] == '1') ;
}

int len = n-k+1, ans = 0 ;
for(int l = 0 ; l < n ; l++)
{
int r = l+len-1 ;
if(r >= n)
break ;
ll curr_cnt = cnt[r] ;
if(l > 0)
curr_cnt -= cnt[l-1] ;
ans += curr_cnt%2 ;
}

cout << ans << '\n' ;
return ;
}

signed main()
{
//fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif

int t = 1;

for(int i=1;i<=t;i++)
{
solve() ;
}

assert(getchar() == -1);
// assert(sum_n <= MAX_SUM_N);

cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n << '\n';
cerr<<"Maximum length : " << max_n << '\n';
cerr << "Sum of product : " << sum_nk << '\n' ;
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
``````
Tester's (Takuki Kurokawa) Solution
``````#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<int> pref(k + 1);
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
pref[max(0, i - (n - k))] ^= 1;
pref[min(k, i + 1)] ^= 1;
}
}
for (int i = 0; i < k; i++) {
pref[i + 1] ^= pref[i];
}
cout << accumulate(pref.begin(), pref.end(), 0) << '\n';
}
return 0;
}
``````
6 Likes

I have solution of O(k), Just use dp to calculate xors and find one by one the calculate the xor of k values.
when going from 2 to n ( nclusive)

dp[i] = dp[i - 1] ^ s[i - 1]

Using this for O(k)
So,
assign variable,

ans = dp[n - k + 1]

The above value is basically xor of all LSB of âkâ length binary numbers
Now,

Bit on ith place = (dp[n - i + 1] ^ dp[k - i])

This only possible as inversion of XOR is XOR itself

Above XOR is the value from k-1 to 1 bits of k bit numbers

I am new so please excuse the formatting

3 Likes

Can any one tell me why my code is giving runtime error on task 2:

my code â

void solve(){
int t;
cin>>t;
while(tâ){
int n,k;
cin>>n>>k;
string s;
cin>>s;
lli res = 0;
for(int i=0;i<n-k+1;i++){

``````     res = res xor stoi(s.substr(i,k),0,2);
}
cout<<__builtin_popcount(res)<<endl;

}
``````

}

1 Like

Some binary num which can be greater than integer limit, so stoi throws a runtime error

4 Likes

please anyone tell why my this sliding window approach giving TLE?? its O(N) operation

#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long

ll countSetBits(ll n)
{
ll count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}
int main(){
fastio();
/#ifndef ONLINE_JUDGE
freopen(âinput.txtâ,ârâ,stdin);
freopen(âoutput.txtâ,âwâ,stdout);
#endif
/
ll t;
cin>>t;
//t=1;
while(tâ){
ll n,k;cin>>n>>k;
string s;
cin>>s;
ll i=0,j=0;
ll total=0,prev=-1,ans=-1,res=-1;
while(j<=n-1){

total=2*(total)+(s[j]-â0â);

ll sz=j-i+1;
if(sz<k){ j++;continue;}

else if(sz==k){

``````res=total;
if(ans==-1)
ans=res;
else
ans = ans^(total);
``````

total= total-(int)pow(2,j-i)*(s[i]-â0â);
i++;
j++;
}
}
cout<<countSetBits(ans)<<endl;
}
return 0;
}

First thing is you canât represent more then 64 bits in a number(C++), so you canât represent string of size K as a number.
Also power function of C++ takes O(N) time so when you are trying to use power function complexity is O(N^2) so you got tle before you get WA.

5 Likes

oh thanks!

Taking long long int wonât help??

Using long long int wonât help??

Nope, long long int is 64 bits only, and K can be till 100000.

2 Likes

``````   int n=input.nextInt();
int k=input.nextInt();
String s=input.next();

int noOfsubstring=n-k+1;

String ss[]=new String[noOfsubstring];
int ans=0;

for(int i=0;i+k<=s.length();i++){
ss[i]=s.substring(i,i+k);

int pp=Integer.parseInt(ss[i],2);
ans=ans^pp;
}

String hh=Integer.toBinaryString(ans);

int count=0;
for(char c: hh.toCharArray())
if(c=='1')
count++;

System.out.println(count);

}

``````