shil love xor problem from divide by zero contest.

arpit728 · January 31, 2016, 10:45am

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.

h1ashdr_gon · January 31, 2016, 10:52am

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

ankg · January 31, 2016, 10:58am

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 on alt 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

thedark · January 31, 2016, 10:58am

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.

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.

vsp4 · January 31, 2016, 10:59am

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

hokagenaruto · February 1, 2016, 9:43pm

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