XORIT - Editorial

editorial
, , , ,
21

Great Explanation!

1 Like
22

Okay Iā€™ll try to!

2 Likes
23

Thanks for the video. Keep up the good job.

1 Like
24

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)
25

Superb explanation!

1 Like
26

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

1 Like
27

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ā€¦

28

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

1 Like
30

Okay, for 12 ,

A = 4, B = 8, NOT 10

31

Thanku!! Nice explanation

1 Like
32

you can check out this tutorial for PRFYIT

33

oh yes got my mistake thank u so muchh

34

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!!

35

Can you please tell how are we saying that A+B=N when the operation mentioned is A^B= N, please help!

36

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
37

This part is very beautiful

1 Like
38

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.

I will be answering your question with proof now :

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 :slight_smile:

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
39

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.

40

Awesome explanation!

41

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?