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.
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
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
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.
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
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
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.
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.
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.
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.
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
why ans is 3 for n=0.