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. asked 31 Jan '16, 10:45

There is a simple series which can be observed. The code can be found here. answered 30 Mar '16, 01:29
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.
(30 Mar '16, 17:23)
why ans is 3 for n=0.
(30 Mar '16, 19:10)

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 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 n1 and for rest of all inputs answer will be 1. Hope this helps. Refer this solution answered 31 Jan '16, 10:58
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.
(30 Mar '16, 17:22)
why ans is 3 for n=0.
(30 Mar '16, 18:14)

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 answered 31 Jan '16, 10:59
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.
(30 Mar '16, 17:23)
why ans is 3 for n=0.
(30 Mar '16, 19:11)

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(m1),......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 answered 01 Feb '16, 21:43
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.
(30 Mar '16, 17:24)
why ans is 3 for n=0.
(30 Mar '16, 19:12)
