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

×

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.

asked 31 Jan '16, 10:45

arpit728's gravatar image

2★arpit728
6831353
accept rate: 10%


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

link

answered 30 Mar '16, 01:29

haresh_kh's gravatar image

3★haresh_kh
563
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) arpit7282★

@haresh_kh

why ans is 3 for n=0.

(30 Mar '16, 19:10) arpit7282★

@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

link

answered 31 Jan '16, 10:58

ankg's gravatar image

3★ankg
2113
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) arpit7282★

@ankg

why ans is 3 for n=0.

(30 Mar '16, 18:14) arpit7282★

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

link

answered 31 Jan '16, 10:52

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2802319
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) arpit7282★

@h1ashdr@gon

why ans is 3 for n=0.

(30 Mar '16, 19:10) arpit7282★

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.

link

answered 31 Jan '16, 10:58

thedark's gravatar image

4★thedark
842
accept rate: 9%

edited 31 Jan '16, 11:00

@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) arpit7282★

@thedark

why ans is 3 for n=0.

(30 Mar '16, 19:11) arpit7282★

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

link

answered 31 Jan '16, 10:59

vsp4's gravatar image

6★vsp4
1.2k128
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) arpit7282★

@vsp4

why ans is 3 for n=0.

(30 Mar '16, 19:11) arpit7282★

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

link

answered 01 Feb '16, 21:43

hokagenaruto's gravatar image

5★hokagenaruto
103
accept rate: 0%

edited 01 Feb '16, 21:44

@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) arpit7282★

@hokagenaruto

why ans is 3 for n=0.

(30 Mar '16, 19:12) arpit7282★
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,040
×1,919
×914
×280
×13

question asked: 31 Jan '16, 10:45

question was seen: 2,030 times

last updated: 30 Mar '16, 19:12