# ENGXOR - Editorial

Tester: Suchan Park
Editorialist: William Lin

Simple

Bits, Basic Math

# PROBLEM:

You are given an array A and you need to answer Q independent queries. For each query, you are given an integer P. You need to first output the number of i such that A_i \oplus P has an even number of set bits in its binary representation and then output the number of i such that A_i \oplus P has an odd number of set bits in its binary representation.

# QUICK EXPLANATION:

Only the parity of the number of set bits in P matters, so we can reduce the queries to either P=0 or P=1. We can just precalculate the answer for both cases.

# EXPLANATION:

Whenever we are working with bitwise operations (like in this problem), it is a good idea to consider the bits individually (separating the bits based on their position), since in bitwise operations, bits from different positions donâ€™t interfere with each othet. Letâ€™s make the problem easier: elements in A and P can only be either 0 or 1.

Under this case, the elements which have an even number of set bits will be 0 and the numbers which have an odd number of set bits will be 1.

To answer a query with a given P, it is pretty easy: If P=0, we first output the number of 0-s in A then output the number of 1-s in A. If P=1, we first output the number of 1-s in A (because those 1-s become 0-s in B) and then we output the number of 0-s in A (because those 0-s become 1-s in B). The only thing we need to do before answering the queries is to count the number of 0-s in A and the number of 1-s in A. Then, we can answer each query in constant time.

Letâ€™s make this problem slightly harder: The elements in A are not restricted to be only 0 or 1, but P still has to be 0 or 1. What if P=0? In this case, A doesnâ€™t change, so we first output the number of elements in A with an even number of set bits then output the number of elements in A with an odd number of set bits.

What if P=1? If x is some number and we xor it with 1, only the last bit of x will change. For example, if x=1001_2, then x \oplus 1 = 1000_2, and if x=10_2, x \oplus 1 = 11_2.

We can notice that the number of set bits in x either increases by 1 (when the last bit changes from 0 to 1) or decreases by 1 (when the last bit changes from 1 to 0). In either case, we notice that the parity of the number of set bits must change: if x has an even number of bits, then x \oplus 1 will have an odd number of bits, and if x has an odd number of bits, x \oplus 1 will have an even number of bits.

So, for queries with P=1, we first output the number of elements in A with an odd number of set bits and then output the number of elements in A with an even number of set bits. We just need to precalculate these two quantities before answer queries.

Letâ€™s move on to the general case with no more constraint on P. Letâ€™s consider all the set bits of P. Like in the case with P=1, each set bit of P will modify the corresponding bit in A_i after the xor, causing that bit to change.

In fact, if P has z set bits, then exactly z bits in A_i will change after the xor. Like in the previous case, each changed bit in A_i causes a change in the parity of the number of set bits in A_i. So if z=3, the parity of the number of set bits in A_i will change 3 times. Suppose that A_i had an odd number of set bits, then the final parity of the number of set bits of A_i will be odd -> even -> odd -> even.

Notice that 2 changes in the parity is equivalent to no change at all (odd -> even -> odd), so only the parity of z matters. So, our solution for the general case is very similar to the case where P can only be 0 or 1: if z=0, we pretend that P=0 and if z=1, we pretend that P=1.

The time complexity should be O(N+Q) or O((N+Q)\log A) depending on implementation.

# IMPLEMENTATION:

As for finding the number of set bits in an integer, we can use the standard algorithm for finding the digits for a number in any base (in this case the base is 2). The code is below:

``````int numBits=0;
while(x>0) {
numBits+=x%2;
x/=2;
}
``````

There are also library functions for certain languages to do this, like `__builtin_popcount(x)` for C++ and `Integer.bitCount(x)` for Java.

Also, as @kabirsingh2027 mentioned below, we can use `__builtin_parity(x)`, which will return `__builtin_popcount(x)%2`.

# HIDDEN TRAPS:

• Make sure you use fast I/O, even the problem statement reminds you to do so! You can test if your input is fast enough with this problem. Make sure to not use â€śendlâ€ť for C++ (and donâ€™t flush when unnecessary with all languages in general).

# SOLUTIONS:

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

#define int long long int
#define endl "\n"
int32_t main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n,q;
cin>>n>>q;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int odd=0,even=0;
for(int i=0;i<n;i++)
{
int check=__builtin_popcount(a[i]);
if( check%2==0)
even++;
else
odd++;
}
while(q--)
{
int input;
cin>>input;
int odd1=odd,even1=even;
int nodd=0,neven=0;
int check1=__builtin_popcount(input);
if(check1%2!=0)
{

odd1=even;
even1=odd;

}
cout<<even1<<" "<<odd1<<endl;
}

}
return 0;
}
``````
Tester's Solution
``````#include <bits/stdc++.h>

const int BUFFER_SIZE = int(1.1e5);

char _buf[BUFFER_SIZE + 10];
int _buf_pos, _buf_len;

char seekChar() {
if(_buf_pos >= _buf_len) {
_buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
_buf_pos = 0;
}
assert(_buf_pos < _buf_len);
return _buf[_buf_pos];
}

bool seekEof() {
if(_buf_pos >= _buf_len) {
_buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
_buf_pos = 0;
}
return _buf_pos >= _buf_len;
}

char ret = seekChar();
_buf_pos++;
return ret;
}

int readInt(int lb, int rb) {
char c = readChar();
int mul = 1;
if(c == '-') {
mul = -1;
}
assert(isdigit(c));

long long ret = c - '0';
int len = 0;
while(!seekEof() && isdigit(seekChar()) && ++len <= 19) {
ret = ret * 10 + readChar() - '0';
}
ret *= mul;

assert(len <= 18);
assert(lb <= ret && ret <= rb);
return (int)ret;
}

char c = readChar();
assert(c == '\n');
//assert(c == '\n' || (c == '\r' && readChar() == '\n'));
}

assert(readChar() == ' ');
}

void run() {
int N = readInt(1, 100000);
int Q = readInt(1, 100000);

int cnt[2] = {0, 0};

for(int i = 0; i < N; i++) {
int a_i = readInt(1, int(1e8));
//if(i + 1 < N) readSpace(); else readEoln();
cnt[__builtin_popcount(a_i) % 2] += 1;
}

for(int q = 0; q < Q; q++) {
int p = readInt(1, int(1e5));
if(q+1 < Q) readEoln();
int c = __builtin_popcount(p) % 2;
printf("%d %d\n", cnt[c], cnt[1-c]);
}
}

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif

int T = readInt(1, 100);

while(T--) {
run();
if(T > 0) readEoln();
}
return 0;
}
``````
Editorialist's Solution
``````#include <bits/stdc++.h>
using namespace std;

void solve() {
//input
int n, q, c[2]={};
cin >> n >> q;
for(int i=0, a; i<n; ++i) {
cin >> a;
//add a to frequency array based on parity
++c[__builtin_popcount(a)%2];
}

//queries
for(int p; q--; ) {
cin >> p;
//determine the parity of p
int z=__builtin_popcount(p)%2;
//z is the 0s and z^1 (which flips z) is the 1s
cout << c[z] << " " << c[z^1] << "\n";
}
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);

int t;
cin >> t;
while(t--)
solve();
}
``````

Please give me suggestions if anything is unclear so that I can improve. Thanks

24 Likes

hey william , my code is almost same as yours but only manages to get 30 points i dont understand whyâ€¦

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

``````int t;
cin>>t;
while(t--)
{

int n,q;
cin>>n>>q;

int odd_count=0;
int even_count=0;

for(int i=0;i<n;i++)
{	int k;
cin>>k;
if(__builtin_popcount(k)%2)
{
even_count++;

}
else
odd_count++;
}

for(int i=0;i<q;i++)
{
int p;
cin>>p;

if(__builtin_popcount(p)%2!=0)
cout<<even_count<<" "<<odd_count<<endl;
else
cout<<odd_count<<" "<<even_count<<endl;

}

}
``````

}

2 Likes

Look at the hidden traps
Actually, I didnâ€™t specify that you should also not use â€śendlâ€ť. Let me add that.

4 Likes

why it is getting tle?

``````    #include <iostream>

int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
int n;
int q;
std::cin >> n >> q;
int arr[n];
for (int i = 0; i < n; i++)
std::cin >> arr[i];
while (q--) {
int p;
std::cin >> p;
int cntOdd = 0;
int cntEven = 0;
for (int i = 0; i < n; i++) {
int x = p ^arr[i];
if (__builtin_parity(x))
cntOdd++;
else
cntEven++;
}
std::cout << cntEven << " " << cntOdd << "\n";
}
}
return 0;
}
``````

This is O(nq) which is too big for the constraints.

In my solution, after changing `endl` to `"\n"` and adding `ios_base::sync_with_stdio(false);cin.tie(NULL);`, the solution got an A.C.
Anyways, hereâ€™s mine -
`#include <iostream>`
`#include <iomanip>`
`#include <cmath>`
`#include <vector>`
`#include <algorithm>`
`#include <bits/stdc++.h>`

``````        typedef long long int ll;
#define test int t; cin >> t; while(t--)
#define MOD 1000007
using namespace std;

ll countSetBits(ll n)
{
ll count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}

int main (){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
test {

ll n,q;
cin >> n >> q;
ll count=0;
ll a[n];
for(ll i=0;i<n;i++){
cin >> a[i];
if(countSetBits(a[i])%2==1){
count ++;
}

}
for(ll i=0;i<q;i++){
ll p;
cin >> p;
if(countSetBits(p)%2==0){
cout << n-count << " " << count << "\n";
}
else {
cout << count << " " << n-count << "\n";
}
}
}
return 0;
}``````

My solution to engxor https://www.codechef.com/viewsolution/30494808

1 Like

Thanks. I got it where I missed it.
Can you give me some tips that how I can get better in competitive programming? As not much sign of improvement is seen since I have started doing it.

Instead of __builtin_popcount(x) we can directly use __builtin_parity(x)
basically if f(N) represents number of set bits in binary representation of N, then
f(N xor K) = f(N) xor f(K)
where f(x) is __builtin_parity(x), a built-in function in C++.

5 Likes

Wow, didnâ€™t know that, thanks!

1 Like

Why this code got TLE in subtask 2? My approach was little different.

``````import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
public static int parity(int x) {

int y;
y = x ^ (x >> 1);
y = y ^ (y >> 2);
y = y ^ (y >> 4);
y = y ^ (y >> 8);
y = y ^ (y >> 16);

return y & 1;
}

public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int t = Integer.parseInt(br.readLine().trim());
while(t-- > 0) {

Queue<Integer> queue = new ArrayDeque<>();

String[] s1 = br.readLine().trim().split(" ");
int n = Integer.parseInt(s1[0]);
int q = Integer.parseInt(s1[1]);

int[] a = new int[n];
int[] p = new int[q];

String[] s2 = br.readLine().trim().split(" ");

for(int i = 0; i < n; ++i) {
a[i] = Integer.parseInt(s2[i]);
}
for(int i = 0; i < q; ++i)

int even = 0, odd = 0;
int temp = queue.remove();

for(int i = 0; i < n; ++i) {
int par = parity(a[i] ^ temp);
if(par == 0)
++even;
else
++odd;
if(i == n - 1 && !queue.isEmpty()) {
i = -1;
System.out.println(even + " " + odd);
even = 0;
odd = 0;
temp = queue.remove();
}
}
if(queue.isEmpty())
System.out.println(even + " " + odd);
}
}
``````

}

*** HEY I M HIMANSHU I ALSO TEXTED IN YOU IN CODEFORCES
MY QUESTION IS IN CASE OF FOR LOOP CAN WE USE WHILE LOOP?

for(int p; qâ€“; ) {
cin >> p;
//determine the parity of p
int z=__builtin_popcountÂ§%2;
//z is the 0s and z^1 (which flips z) is the 1s
cout << c[z] << " " << c[z^1] << â€ś\nâ€ť;
}

@tmwilliamlin why shouldnâ€™t we use endl?

I donâ€™t understand this part at all!

yes

try fast output for java (printwriter)

We make a simple version of the problem where all elements can only be 0/1.

/* package codechef; // donâ€™t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be â€śMainâ€ť only if the class is public. */
class Codechef
{
public static void main(String[] args) {
PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
//BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
int t;
try {
for (int i = 0; i < t; i++) {
int n, q;
int a[] = new int[n];
int even1s = 0, odd1s = 0;
for (int j = 0; j < n; j++) {
int setBits = countSetBits(a[j]);
if (setBits % 2 == 0) {
even1s++;
} else {
odd1s++;
}
}
for (int j = 0; j < q; j++) {
int p = reader.nextInt();
int setBits = countSetBitsÂ§;
if (setBits % 2 == 0) {
//writer.write();
writer.write(even1s + " " + odd1s + â€ś\nâ€ť);
writer.flush();
} else {
writer.write(odd1s + " " + even1s + â€ś\nâ€ť);
writer.flush();
}
}
}
} catch (Exception e) {
e.printStackTrace();
}
}

``````private static int countSetBits(int num) {
int setBits = 0;
while (num != 0) {
num = num & (num - 1);
setBits++;
}
return setBits;
}

static class FastReader {
private StringTokenizer st;

}

public String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
e.printStackTrace();
}
}
return st.nextToken();
}

public int nextInt() {
return Integer.parseInt(next());
}
``````

}
}
I used PrintWriter and Fast I/O in java still getting TLE in second part

Hereâ€™s my submission for ENGXOR. AC in one go

``````#include <iostream>
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int testCases = 0;
cin >> testCases;
while(testCases--){
int noOfElements = 0;
int noOfQueries = 0;
cin >> noOfElements >> noOfQueries;
int countOfParity[2];
countOfParity[0] = countOfParity[1] = 0;
for(int i = 0 ; i < noOfElements ; ++i){
int temp;
cin >> temp;
int noOfBits = __builtin_popcount(temp);
if(noOfBits%2 == 0) ++countOfParity[0];
else ++countOfParity[1];
}
while(noOfQueries--){
int P;
cin >> P;
int noOfBitsP = __builtin_popcount(P);
if(noOfBitsP%2 == 0){
cout << countOfParity[0] << " " << countOfParity[1] << '\n';
}
else{
cout << countOfParity[1] << " " << countOfParity[0] << '\n';
}
}
}
return 0;
}``````

Good explanation

1 Like