# XORIT - Editorial

Great Explanation!

1 Like

Okay I’ll try to!

2 Likes

Thanks for the video. Keep up the good job.

1 Like

Can I do the below code.I know its complexity will be n^2 but the time it took was 1.01 secs(when converted to c++) ,have a look once and suggest some modification.

for i in range(int(input())):
x,y=input().split()
n=int(x)
m=int(y)
sum=0
def returner(i):
for j in range(1,i+1):
for k in range(j,i+1):
if myXOR(j,k)==i:
return k
break
return -1
def myXOR(x, y):
return ((x | y) & (~x | ~y))
for i in range(n,m+1):
sum=returner(i)+sum

``print(sum)``

Superb explanation!

1 Like

Thank you! I am asking because the editorial is not clear, by the way i like your videos. Way to go!

1 Like

hey can you explain the same for 10 17??
im getting 81 for that
as sum of B comes to be 8+10 +10 +12 +12 +14 -1 +16=81
plss help in clarify
thanks…

Sir, Thank you very much. Can you please make the video for second question. PRFYIT.

1 Like

Okay, for 12 ,

A = 4, B = 8, NOT 10

Thanku!! Nice explanation

1 Like

you can check out this tutorial for PRFYIT

oh yes got my mistake thank u so muchh

Please tell me how are we talking in terms of sum here? Calculating (N-A) when the operation in the question mentioned is clearly XOR? Thanks!!

As explained in the editorial, A and B shouldn’t have any common set bits in their binary representation. Knowing this fact, we can safely say that A + B = A \oplus B since \oplus is the same as addition, only without carry which we know we won’t need in adding A to B.

2 Likes

This part is very beautiful

1 Like

It asks you to find the sum of the values F (N) (which is the value of B) for the provided range [ L … R ].
All the constraints are set to higher values, you need Bit manipulation to get the required answer.

Lets consider 1 to 5 in binary representation :

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1

Now, we know, that the Sum of (1 … 5 ) = 15.

In this case, you consider only the LSB for every bit.
But, now let us calculate this column-wise :

Set Bits in (0th - bit column) = 3 * (2 ^ 0) = 3
Set Bits in (1st - bit column) = 2 * (2 ^ 1) = 4
Set Bits in (2nd - bit column) = 2 * (2 ^ 2) = 8

(8 + 4 + 3) = 15.

Now, if we take into consideration only some of the bits while calculating (as we are doing in LSB calculation, Check my previous explanation.)

The value gets deducted, but it maintains the property. You do not apply xor operation in this optimized approach Here, you just ignore a few bits. Read Bit manipulation or read more carefully.

That is reason why B is SUM(N) - SUM(A), The bits, which you did not take into consideration.

1 Like

This is so good! I got to know that A+B= A^B since A and B must not have any common set bits (as proved in editorial). Thanks.

Awesome explanation!

Can you help explaining this part please? How can we calculate the position of least set bit in order to calculate the value of A?