shil love xor problem from divide by zero contest.

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.

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

@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 Likes

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.

Read this: A003815 - OEIS

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

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

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

6 Likes

@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.

@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.

@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.

@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.

@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.

@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.

@ankg

why ans is 3 for n=0.

@haresh_kh

why ans is 3 for n=0.

@h1ashdr@gon

why ans is 3 for n=0.

@thedark

why ans is 3 for n=0.

@vsp4

why ans is 3 for n=0.

@hokagenaruto

why ans is 3 for n=0.