shil love xor problem from divide by zero contest.

ad-hoc
divide-by-zero
dynamic-programming
editorial
xor

#1

this problem how to solve this question input size is to big, so the precomputation is not possible

Can anyone write editorial to this problem.


#2

Try printing the xor of all numbers from 1 to (say) 100 (separately) and observe the pattern :slight_smile:


#3

@arpit728:

This problem can be done in O(n).

Firstly, write a program for function f(X) and just observe the output for first 20 numbers. below is the image … f(1) = 1, f(2) = 3 , f(3) = 0 … and so onalt text

So now u can observe that the mimimun possible k such that F(k) = 0 is 3. f(7) and f(11) is also 0 but the minimum is 3 and similarly u can oberve that if X is a multiple of 4 then the answer is n itself and if n is in the form of 4*n+3 the answer is n-1 and for rest of all inputs answer will be -1.

Hope this helps.

Refer this solution


#4

After you write it on paper you will see there is a series-

1 = 1 (n = 1)

1^2 = 3 (n = 2)

1^2^3 = 0 (n = 3)

4 = 4 (n = 4)

4^5 =1 (n = 5)

4^5^6 = 7 (n = 6)

4^5^6^7 = 0 (n = 7)

8 =8 (n = 8)

8^9 = 1 (n = 9)

8^9^10 = 11 (n = 10)

8^9^10^11 = 0 (n = 11)

12 = 12
.
.
.

So in general we see that
a series is generated after interval of 4 numbers
So,
1)if n%4==0

then answer is n itself.

2)if (n+1)%4==0

then answer is n-1.

  1. corner cases

    a) when n is 0 answer is 3

    b) when n is 1 answer is 1

rest in all other cases answer is -1.


#5

Read this: https://oeis.org/A003815

Important: a(4n+1)=1, a(4n+2)=4n+3, a(4n+3)=0, a(4n+4)=4n+4, n>=0


#6

This problem can also be solved using DP.
Consider for n>1 xor of(1…2power(n)) is 2 power(n) ;
That means that to make a number n the min value k >=2power(log(n))

Also let the binary representation of the no be am,a(m-1),…a0 where am is the last set bit
Let k1 be the min value such that xor of (1…k1)= k xor 2power(m)
then if k1 is odd its impossible to make as then we would have to xor odd count of no with bit am set (excluding n itself) , which would mean when we take xor with n itself it would become zero.
if k1 is even then min value of k = 2power(m) + cal_ans(k xor 2power(m) )
// see code for more clearity
This can be coded as recursive function with :
cal_ans(0)=0 ;
cal_ans(1)=1 ;
cal_ans(2)=-1 ; // that is 2 is not possible
cal_ans(3)=2 ;

At the end we just need to consider a special case of n==0 for which ans is 3.

For more reference see my code :
https://www.codechef.com/viewsolution/9275604


#7

There is a simple series which can be observed. The code can be found here.


#8

@ankg

Thank you, Can you please tell me, what is the approach to arrive at this kind of solutions. I mean, how to build logic for this kind of problem.


#9

@haresh_kh

Thank you, Can you please tell me, what is the approach to arrive at this kind of solutions. I mean, how to build logic for this kind of problem.


#10

@h1ashdr@gon

Thank you, Can you please tell me, what is the approach to arrive at this kind of solutions. I mean, how to build logic for this kind of problem.


#11

@thedark

Thank you, Can you please tell me, what is the approach to arrive at this kind of solutions. I mean, how to build logic for this kind of problem.


#12

@vsp4

Thank you, Can you please tell me, what is the approach to arrive at this kind of solutions. I mean, how to build logic for this kind of problem.


#13

@hokagenaruto

Thank you, Can you please tell me, what is the approach to arrive at this kind of solutions. I mean, how to build logic for this kind of problem.


#14

@ankg

why ans is 3 for n=0.


#15

@haresh_kh

why ans is 3 for n=0.


#16

@h1ashdr@gon

why ans is 3 for n=0.


#17

@thedark

why ans is 3 for n=0.


#18

@vsp4

why ans is 3 for n=0.


#19

@hokagenaruto

why ans is 3 for n=0.