Hello Coders,
As I know many of you were near to solution but got wrong answers in this question. Here is my solution and you can even ask your doubts in your logic here…
Problem link :
[Contest(div1)][1]
[Contest(div2)][2]
[Practice][3]
Author : [Yuri][4]
DIFFICULTY: Easy
Short description of problem :
Making XOR of N elements as big as possible by using integers from 1 to K.
Explaination :
First of we need to know the most significant bit which is 1 in binary representation of number K (i.e. the first bit which is 1 from left side) .
This, can be done in many ways… simplest way is taking \lfloor log_2(k) \rfloor +1 (i.e. taking its floor function which is, obviously, typecasted to int)
Now we have the position of Most Significant Bit, starting from rightmost bit.
(Alternate: It can also be done by a for loop (hint : using k/=2 and k\%2 ) )
Now the MAX XOR value we can achieve in best possible case is all 1's till (and including) the most significant bit.
Example- If position was 3 then MAX XOR we can achieve is-
111_2 (in binary) == 7 in decimal.
So basically MAX XOR is nothing but {2}^{(p)}-1 where p is position of MSB from right (1-based indexing) .
Note that, there can’t be any 1 at left side of MSB (Most Significant Bit) in binary representation in any number 1 to K , else the number will become >K, violating the conditions.
Taking an example-
Click to view
Lets assume K to be 9 == 1001_2
then MAX XOR can be 1111_2 in binary… as simple as that…
In every case we can achieve the MAX XOR except some special cases like
1)N==1 (answer is K)
2)K==1 and N is even (answer is n times 1… hence XOR will be 0)
3)K==2 and N is odd ( answer is 2 followed by (N-1) times 1’s… where XOR would be 2)
Otherwise XOR of all can be achieved as all the number of bits counted are 1…
If your Output satisfies above explanation then your solution will definitely give AC…
How to achieve MAX XOR for given N and K ?
Well there are many methods by which this can be done…
In fact only two numbers 1\leq number \leq K can achieve MAX XOR… and we can even make three numbers such that their XOR is the MAX XOR possible(i.e all 1's in binary).
Let me explain you how…
If K = 9 = 00001001_2
then find temp = 00001000_2 (keep every bit except the leftmost bit which is 1 in K as 0).
code for which would be…
temp = pow(2, (int) log2(k));
1) Achieving MAX XOR by using Two numbers less than k is …
temp \oplus temp-1 = 00001000_2 \oplus 00000111_2 = 00001111_2.
2) Achieving MAX XOR by using Three numbers less than k is …
temp \oplus temp-2 \oplus 1 = 00001000_2 \oplus 00000110_2 \oplus 00000001_2 = 00001111_2.
which are MAX XOR…
$
