KMXOR - Editorial (Unofficial) (As i know many of you were near to the solution and you r getting wrong answers)

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 :


Author : [Yuri][4]


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…


$ #### It is fact that if $K>3$ .... #1 $ \leq temp , temp-1 , temp-2 \leq$ K (?Why.. Think :D) #### Now you might be thinking why we just found two ways of maxing the $MAX XOR$ with $Two$ and $Three$ numbers.. Because that was the $main solution$... Let me Explain that... Now as we know #y $\oplus$ y = 0 and y $\oplus$ 0 = y which do you think is the number which all $1$ $to$ $K$ will contain..( $1$ itself isn't it :D) ## Two cases : # N is even : print (temp-1) (temp) (1) (1) (1)... n terms # N is odd : print (temp-2) (temp) (1) (1) (1)... n terms Obviously Don't print brackets... #### So this is applicable when only K>3... (why not for k$\leq$3 ? take this as homework.. :) ) We had already discussed partial answer for k=1,2,3... Lets complete them... ### K==1 we don't have any choice rather than printing 1's .... ### K==2 print 2 followed by (N-1) times 1 ..... (why? think...) ### K==3 N is odd : print 3 followed by (N-1) 1's .... N is even : print 2 followed by (N-2) 1's .... #### MY SOLUTION LINK: ### Sample [Solution][5] [1]: [2]: [3]: [4]: [5]:

PS: sorry I saw the official editorial after I posted this one… Now I think I should let it be as maybe someone can get a help…

1 Like

Its my first attempt for writing editorial so please forgive me for my english and length of editorial…

1 Like

Thanks, I_returns. I almost solved the question just missed the edge cases! and lost 100 ratings got back to Div B :frowning:

ohh… welcome :slight_smile:

My suggestion to people getting wrong answer is try this test case :
4 1
5 1
5 2
6 2
5 3
6 3
5 8
2 8
4 8
answer: XOR of all should be…

And don’t forget to check whether all are in range 1 to K…
And please do count numbers you are printing whether they are exactly N or not

1 Like

perfect, thanks for pointing out the edge cases. Finally got AC.

I am getting right in all the test cases mentioned above but still getting wrong answer

welcome :slight_smile:

for "5 8 " you forgot to print two one’s …

corrected still getting wrong answer …sorry but please have a look at it…i have written the code neatly though

okay sure… give me some minutes…

I am getting right in all the test case mentioned above but still getting wa please have a look at it.

Your logic is correct… got AC after some typecasting…

just type cast the output of pow(x,y) function to (ll) and that’s it…

ya sure… wait…

Your logic is also correct typecast problem…

here is your accepted soln

here is your accepted soln… didn’t knew what was float(x)…

Thanks bro.

1 Like