XOR_EQ_SUM - Editorial


Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: emptypromises
Tester and Editorialist: iceknight1093




Familiarity with bitwise operations and binary representations


Given L and R, find the number of integers x such that there exist L \leq a \leq b \leq R satisfying a+b = a\oplus b = x.


First off, a + b = a\oplus b means that a and b must have completely disjoint binary representations, i.e, a\ \&\ b = 0.
With that in mind, let’s go over the subtasks.

Subtask 1

The limits here are very small, simply iterate over all pairs of (a, b), and if they satisfy the condition insert their sum into a set.
The answer is the size of the set.

The trivial implementation of this takes \mathcal{O}((R - L)^2 \log {(R - L)}) time, which is good enough.

Subtask 2

Here, we have L = 0 and R = 2^k - 1, i.e, all numbers with at most k significant bits.
It’s possible to make every number from L to R here, since to make x we can choose a = 0 and b = x.

Making anything \gt R is impossible, because the xor of two k-bit numbers cannot have \gt k significant bits.

So, the answer is the length of the range [0, R], which is R+1.
Note that R+1 = 2^k, so the answer essentially says we can make all k-bit strings.

Subtask 3

Here, we still have L = 0, though we might not have R = 2^k - 1.

With the same logic as the previous subtask, we can certainly make all x in the range [0, R].
However, we might now be able to reach x \gt R as well (for example, if R = 2 we can reach 3 = 1+2 = 1\oplus 2).

In fact, if R is a k-bit number, we can reach all the k-bit numbers!


Let R be a k-bit number, i.e, k is the smallest integer such that R \leq 2^k - 1.
Then, certainly we must have 2^{k-1} \leq R.

Any k-bit integer x\geq 2^{k-1} can be reached by choosing b = 2^{k-1} and a = x - b.
Note that this works because a \lt 2^{k-1}.

Numbers \leq R can be formed trivially by (0, x) as noted eariler; and this method allows us to form all the numbers from R+1 to 2^k - 1, so we’re done.

This gives us a simple solution: if R is a k-bit integer, the answer is just 2^k.

Finding k requires us to find the highest set bit in R, which can be done by just iterating k from 0 — it’ll take \mathcal{O}(\log R) time which is good enough.

Subtask 4

The constraints here allow for a linear (or close to linear) solution.

Note that any valid x must be \leq 2R.
So, let’s iterate over each x from 0 to 2R and see if we can make it.
If x = 0, then we can make it with (0, 0) if L = 0, and can’t make it otherwise.

If x \gt 0, then we can write its binary representation as x = 2^{p_1} + 2^{p_2} + \ldots + 2^{p_m} where p_1 \gt p_2 \gt \ldots \gt p_m.
To write x = a\oplus b = a + b, we need to distribute the bits p_1, p_2, \ldots, p_m to a and b.
Clearly, since b is the larger one, it must receive 2^{p_1}.
After this, it’s best to give all remaining 2^{p_i} to a, since:

  • Increasing b too much might make it exceed R
  • Keeping a too small might leave it \lt L

So, the best chance we have is with a = 2^{p_2} + 2^{p_3} + \ldots + 2^{p_m} and b = 2^{p_1}.
That is, b = 2^{p_1} and a = x \oplus b.
Form these a and b, and check if they both lie in [L, R].
If they do, increase the answer by 1.

The check for each x can be done in \mathcal{O}(1) or \mathcal{O}(\log x), and we check upto 2R different values of x so this takes \mathcal{O}(R\log R) time, which is good enough.

Subtask 5

Now, L and R are too large for any linear-type solutions to work.

Let’s look back at how we solved subtask 4:

  • We fixed a value of x between 1 and 2R (0 was special-cased out)
  • We found the highest bit of x and gave it to b; and gave all the other bits of x to a
  • Then, we checked if this a and b were in range [L, R].

Notice the second point in particular: the only b we care about are powers of 2.
So, let’s fix b as a power of 2 in the range [L, R] and see which values of a are valid, as per our algorithm.

  • First off, by our construction we must have a \lt b.
  • We also must have a \geq L.
  • It’s not hard to see that any such a is valid; i.e, we can choose any a in the range [L, b-1].
    The length of this range is b - L.

This gives us a pretty simple algorithm:

  • Fix the value of b to some power of 2 that lies in [L, R].
  • Then, add b - L to the answer.

If L = 0, add 1 to the answer since we can also form x = 0.

Since we only care about powers of 2 that don’t exceed R, we check \log R of them.
So, this algorithm takes \mathcal{O}(\log R) time, which is fast enough to get AC.


\mathcal{O}(\log R) per test case.


Author's code (C++)
#include <bits/stdc++.h>
using namespace std;

int main() {
	int T;
	cin >> T;
	assert(1 <= T && T <= 1e5);
	while (T--) {
		long long l, r;
		cin >> l >> r;
		assert(0 <= l && l <= r && r <= 1e18);
		long long ans = 0;
		for (int b = 0; b < 60; b++) {
			long long msb = (1LL << b);
			if (l <= msb && msb <= r) {
				ans += msb - l;
		if (l == 0) {
		cout << ans << '\n';
	return 0;
Editorialist's code (Python)
for _ in range(int(input())):
    l, r = map(int, input().split())
    ans = 1 if l == 0 else 0
    for pw in range(60):
        if 2**pw > r: break
        if 2**pw < l: continue
        ans += 2**pw - l

This problem can also be solved using digit dp. At first I thought it would get TLEd because it performs 3.84*1e8 operations and time limit is 1sec, but somehow it passed.


beautiful Question, Bro…, It took me 36 hrs to make final observation…