You are not logged in. Please login at www.codechef.com to post your questions!

×

# shil love xor problem from divide by zero contest.

 0 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 1★arpit728 683●18●68 accept rate: 10%

 6 There is a simple series which can be observed. The code can be found here. answered 30 Mar '16, 01:29 56●4 accept rate: 25% @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. (30 Mar '16, 17:23) arpit7281★ @haresh_kh why ans is 3 for n=0. (30 Mar '16, 19:10) arpit7281★
 4 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 n-1 and for rest of all inputs answer will be -1. Hope this helps. Refer this solution answered 31 Jan '16, 10:58 3★ankg 211●3 accept rate: 33% @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. (30 Mar '16, 17:22) arpit7281★ why ans is 3 for n=0. (30 Mar '16, 18:14) arpit7281★
 0 Try printing the xor of all numbers from 1 to (say) 100 (separately) and observe the pattern :) answered 31 Jan '16, 10:52 291●2●3●20 accept rate: 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. (30 Mar '16, 17:23) arpit7281★ @h1ashdr@gon why ans is 3 for n=0. (30 Mar '16, 19:10) arpit7281★
 0 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. 3) 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. answered 31 Jan '16, 10:58 4★thedark 84●2 accept rate: 9% @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. (30 Mar '16, 17:23) arpit7281★ @thedark why ans is 3 for n=0. (30 Mar '16, 19:11) arpit7281★
 0 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 6★vsp4 1.2k●1●3●8 accept rate: 28% @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. (30 Mar '16, 17:23) arpit7281★ @vsp4 why ans is 3 for n=0. (30 Mar '16, 19:11) arpit7281★
 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 answered 01 Feb '16, 21:43 10●3 accept rate: 0% @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. (30 Mar '16, 17:24) arpit7281★ @hokagenaruto why ans is 3 for n=0. (30 Mar '16, 19:12) arpit7281★
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,851
×2,211
×968
×304
×13

question asked: 31 Jan '16, 10:45

question was seen: 2,097 times

last updated: 30 Mar '16, 19:12