 # 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) {
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;
}

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

}

void run() {

int cnt = {0, 0};

for(int i = 0; i < N; i++) {
cnt[__builtin_popcount(a_i) % 2] += 1;
}

for(int q = 0; q < Q; q++) {
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

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

void solve() {
//input
int n, q, c={};
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
{
while(t-- > 0) {

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

int n = Integer.parseInt(s1);
int q = Integer.parseInt(s1);

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

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 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;
}

private StringTokenizer st;

}

public String next() {
while (st == null || !st.hasMoreElements()) {
try {
} 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;
countOfParity = countOfParity = 0;
for(int i = 0 ; i < noOfElements ; ++i){
int temp;
cin >> temp;
int noOfBits = __builtin_popcount(temp);
if(noOfBits%2 == 0) ++countOfParity;
else ++countOfParity;
}
while(noOfQueries--){
int P;
cin >> P;
int noOfBitsP = __builtin_popcount(P);
if(noOfBitsP%2 == 0){
cout << countOfParity << " " << countOfParity << '\n';
}
else{
cout << countOfParity << " " << countOfParity << '\n';
}
}
}
return 0;
}``````

Good explanation

1 Like